Piecewise linear activations substantially shape the loss surfaces of neural networks
Authors: Fengxiang He
Bohan Wang
Dacheng Tao
Venue:  (2020)
Keywords: neural network
nonlinear activation
loss surface
spurious local minimum

Abstract: Understanding the loss surface of a neural network is fundamentally important to the understanding of deep learning. This paper presents how piecewise linear activation functions substantially shape the loss surfaces of neural networks. We first prove that {\it the loss surfaces of many neural networks have infinite spurious local minima} which are defined as the local minima with higher empirical risks than the global minima. Our result demonstrates that the networks with piecewise linear activations possess substantial differences to the well-studied linear neural networks. This result holds for any neural network with arbitrary depth and arbitrary piecewise linear activation functions (excluding linear functions) under most loss functions in practice. Essentially, the underlying assumptions are consistent with most practical circumstances where the output layer is narrower than any hidden layer. In addition, the loss surface of a neural network with piecewise linear activations is partitioned into multiple smooth and multilinear cells by nondifferentiable boundaries. The constructed spurious local minima are concentrated in one cell as a valley: they are connected with each other by a continuous path, on which empirical risk is invariant. Further for one-hidden-layer networks, we prove that all local minima in a cell constitute an equivalence class; they are concentrated in a valley; and they are all global minima in the cell.

Published as a conference paper at ICLR 2020
PIECEWISE LINEAR ACTIVATIONS SUBSTANTIALLY SHAPE THE LOSS SURFACES OF NEURAL NETWORKS
Fengxiang He, Bohan Wang" & Dacheng Tao
UBTECH Sydney AI Centre, School of Computer Science, Faculty of Engineering
The University of Sydney Darlington, NSW 2008, Australia
(fengxiang.. he, dacheng. tao @sydney edu au, bhwangfyegmail.com
ABSTRACT
Understanding the loss surface of neural network is fundamentally important to the understanding of deep learning. This paper presents how piecewise linear activation functions substantially shape the loss surfaces of neural networks. We first prove that the loss surfaces of many neural networks have infinite spurious local minima which are defined as the local minima with higher empirical risks than the global minima. Our result demonstrates that the networks with piecewise linear activations possess substantial differences the well-studied linear neural networks. This result holds for any neural network with arbitrary depth and arbi- trary piecewise linear activation functions (excluding linear functions) under most loss functions in practice. Essentially, the underlying assumptions are consistent with most practical circumstances where the output layer is narrower than any hid- den layer. In addition, the loss surface of neural network with piccewise linear activations is partitioned into multiple smooth and multilinear cells by nondiffer- entiable boundaries. The constructed spurious local minima are concentrated in one cell as a valley: they are connected by a continuous path, on which empirical risk is invariant. Further for one-hidden-llyer networks, we prove that all local minima in cell constitute an equivalence class; they are concentrated in a valley; and they are all global minima in the cell.
INTRODUCTION
Neural networks have been successfully deployed in many real-world applications (LeCun et al., 2015; Witten al., 2016; Silver al., 2016; He et al., 2016; Litjens et al., 2017). In spite of this, the theoretical foundations in our knowledge of deep learning theory, the investigation into the loss surfaces of neural networks is of fundamental importance. Understanding the loss surface would be helpful in several relevant research areas, such as the ability to estimate data distributions, the optimization of neural networks, and the generalization to unseen data.
neural networks are somewhat premature. To the many deficiencies
This paper studies the role of the nonlinearities in activation functions in shaping the loss surfaces of neural networks. Our results demonstrate that the impact of nonlincarities is profound.
First, we prove that the loss surfaces of nonlinear neural networks are substantially different those of linear neural networks, in which local minima are created equal, and also, they are all global minima (Kawaguchi, 2016; Baldi Hornik, 1989; Lu & Kawaguchi, 2017; Freeman & Bruna, 2017; Zhou & Liang, 2018; Laurent & von Brecht, 201 8; Yun et al., 2018). By contrast,
Neural networks with arbitrary depth and arbitrary piecewise linear activa- tions (excluding linear functions) have infinitely many spurious local minima der arbitrary continuously differentiable loss functions.
Both authors contributed equally.
"Boaan Wang is also affiliated with University of Science and Technology of China. This work was com- pleted when he was summer intern at UBTECH Sydney Al Centre, School of Computer Science, Faculty of Engineering, the University of Sydney.

---

Published as a conference paper at ICLR 2020
This result only relies on four mild assumptions that cover most practical cireumstances: (1) the training sample set is linearly inseparable; (2) all training sample points are distinct; (3) the output layer is narrower than the other hidden layers; and (4) there exists some turning point in the piece- wise linear activations that the sum of the slops on the two sides does not equal to O.
Our result significantly extends the existing study on the existence of spurious local minimum. For example, Zhou & Liang (2018) prove that one-hidden-layer neural networks with two nodes in the hidden layer and two-piece linear (ReLU-like) activations have spurious local minima; Swirszez et al. (2016) prove that ReLU networks have spurious local minima under the squared loss when most of the neurons are not activated; Safran & Shamir (2018) present computer-assisted proof that two-layer ReLU networks have spurious local minima; a recent work (Yun et al., 2019b) have proven that neural networks with two-piece linear activations have infinite spurious local minima, but the results only apply to the networks with one hidden layer and one-dimensional outputs; and a concurrent work (Goldblum et al., 2020) proves that for multi-layer perceptrons of any depth, the performance of every local minimum on the training data equals to a linear model, which is also verified by experiments.
The proposed theorem is proved in three stages: (1) we prove that neural networks with one hidden layer and two-piece linear activations have spurious local minima; (2) we extend the conditions to neural networks with arbitrary hidden layers and two-piece linear activations; and (3) we further ex- tend the conditions to neural networks with arbitrary depth and arbitrary piecewise linear activations. Since some parameters of the constructed spurious local minima are from continuous intervals, we have obtained infinitely many spurious local minima. At each stage, the proof follows a two-step strategy that: (a) constructs an infinite series of local minima; and (b) constructs a point in the pa- rameter space whose empirical risk is lower than the constructed local minimum in Step (a). This strategy inspired by Yun et al. (2019b) but we have made significant and non-trivial development.
Second, we draw a "big picture" for the loss surfaces of nonlinear neural networks. Soudry & Hoffer (2018) highlight smooth and multilinear partition of the loss surfaces of neural networks. The nonlinearities in the piecewise linear activations partition the loss surface of any nonlinear neural network into multiple smooth and multilinear open cells. Specifically, every nonlinear point in the activation functions creates group of the non-differentiable boundaries between the cells, while the linear parts of activations correspond to the smooth and multilinear interiors. Based on the partition, we discover degenerate nature of the large amounts of local minima from the following aspects:
Every local minimum is globally minimal within cell. This property demonstrates that the local geometry within every cell is similar to the global geometry of linear networks, although technically, they are substantially different. It applies to any one-hidden-layer neural network with two-piece linear activations for regression under convex loss. We rig- orously prove this property in two stages: (1) we prove that within every cell, the empirical risk R is convex with respect to a variable W mapped from the weights W by mapping Q. Therefore, the local minima with respect to the variable W are also the global minima in the cell; and then (2) we prove that the local optimality is maintained under the constructed mapping. Specifically, the local minima of the empirical risk R with respect to the param- eter W are also the local minima with respect to the variable W. We thereby prove this property by combining the convexity and the correspondence of the minima. This proof is technically novel and non-trivial, though the intuitions are natural.
Equivalence classes and quotient space of local minimum valleys. All local minima in a cell are concentrated as a local minimum valley: on a local minimum valley, all local minima are connected with each other by a continuous path, on which the empirical risk is invariant. Further, all these local minima constitute an equivalence class. This local minima valley may have several parallel valleys that are in the same equivalence class but do not appear because of the restraints from cell boundaries. If such constraints are ignored, all the equivalence classes constitute a quotient space. The constructed mapping Q is exactly the quotient map. This result coincides with the property of mode connectivity that the minima found by gradient-bases methods are connected by a path in the parameter space with almost invariant empirical risk (Garipov et al., 2018; Draxler et al., 2018; Kuditipudi et al., 2019). Additionally, this property suggests that we would need to study every local minimum valley as whole.
2

---

Published as a conference paper at ICLR 2020
Linear collapse. Linear neural networks are covered by our theories simplified case. When all activations are linear, the partitioned loss surface collapses to one single cell, in which all local minima are globally optimal, as suggested by the existing works linear networks (Kawaguchi, 2016; Baldi & Hornik, 1989; Lu & Kawaguchi, 2017; Freeman & Bruna, 2017; Zhou & Liang, 2018; 8; Laurent & von Brecht, 2018; Yun et al., 2018).
Notations. If M a matrix, Mi, denotes the (i, component of M. If M vector, M; denotes the i-th component of M. Define Fgy as a matrix in which the (i.j)-th component is while all other components are 0. Also, denote e, as a vector such that the i-th component is while all others are O. Additionally, we define 1; E gxx1 is vector whose components are all 1, while those of Oxmm E R2xm (or briefly, 0) are all O. For the brevity, [i j] denotes fi,.., ,57.
RELATED WORK
Some works suggest that linear neural networks have no spurious local minima. Kawaguchi (2016) proves that linear neural networks with squared loss do not have any spurious local minimum under three assumptions about the data matrix X and the label matrix Y: (1) both matrices XX" and XY have full ranks; and (2) the input layer is wider than the output layer; and (3) the eigenvalues
of matrix X (Xx*)= XY are distinct with each other. Zhou & Liang (2018) give an analytic formulation of the critical points for the loss function of deep linear networks, and thereby obtain a group of equivalence conditions for that critical point is a global minimum. Lu & Kawaguchi (2017) prove the argument under one assumption that both matrices X and Y have full ranks, which even more restrictive. However, in practice, the activations of most neural networks are not linear. The nonlinearities would make the loss surface extremely non-convex and even non-smooth and therefore far different from the linear case.
The loss surfaces of over parameterieee neural networks have some special properties. Choroman- ska et al. (2015) empirically suggest that: (I) most local minima of over-paramettrrized networks are equivalent; and (2) small-size networks have spurious local minima but the probability of finding one decreases rapidly with the network size. Li et al. (2018) prove that over weer-pramettrizee fully- connected deep neural networks with continuous activation functions and convex, differentiable loss functions, have no bad strict local minimum. Nguyen et al. (2019) suggest that "sufficiently over- parameterized" neural networks have no bad local valley under the cross-entropy loss. Nguyen (2019) further suggests that the global minima of sufficiently wver-parameterized neural networks are connected within a unique valley. Many other works study the convergence, generalization, and other properties of stochastic gradient descent on the loss surfaces of over-pane parameterized networks (Chizat & Bach; Arora al., 2018; Brutzkus et al., 2018: Du al., 2019; Soltanolkotabi et al., 2018; Allen-Zhu et al., 2019a;b; Oymak & Soltanolkotabi, 2019).
Many advances on the loss surfaces of neural networks are focused on other problems. Zhou & Feng (2018) and Mei et al. (2018) prove that the empirical risk surface and expected risk surface are linked. This correspondence highlights the value of investigating loss surfaces (empirical risk surfaces) to the study of generalization (the gap between empirical risks to expected risks). Hanin & Rolnick (2019) demonstrate that the input space of neural networks with piecewise linear activations partitioned by multiple regions, while our work focuses the partition of the loss surface. Xie et al. (2017) proves that the training error and test error are upper bounded by the magnitude of the gradient, under the assumption that the geometry discrepancy of the parameter W is bounded. Sagun et al. (2016; 2018) present empirical results that the eigenvalues of the Hessian of the loss surface are two-fold: (1) a bulk centered closed to zero; and (2) outliers away from the bulk. Kawaguchi & Kaelbling (2020) prove that we can climinate the spurious local minima by adding one unit per output unit for almost any neural network in practice. Tian (2017); Andrychowiez et al. (2016); Soltanolkotabi (2017): Zhong et al. (2017); Brutzkus & Globerson (2017): Tian (2017): Li & Yuan (2017); Zou et al. (2019): Li & Liang (2018); Du et al. (2018a: 2019); Zhang et al. (2019b); Zhou et al. (2019); Wang et al. (2019) study the optimization methods for neural networks. Other relevant works include Sagun et al. 2016; 2018); Nguyen & Hein (2018); Du et al. (2018b); Haeffele & Vidal (2017); Liang et al. (2018); Wu et al. (2018): Yun et al. (2019a): Zhang al. (2019a): Kuditipudi et al. (2019); Garipov et al. (2018); Draxler et al. (2018); He et al. (2019); Kawaguchi & Kaelbling (2020).
3

---

Published as a conference paper at ICLR 2020
3 NEURAL NETWORK HAS INFINITE SPURIOUS LOCAL MINIMA
This section investigates the existence of spurious local minima on the loss surfaces of neural net- works. We find that almost all practical neural networks have infinitely many spurious local minima. This result stands for any neural network with arbitrary depth and arbitrary piecewise linear activa- tions excluding linear functions under arbitrary continuously differentiable loss.
3.1 PRELIMINARIES
Consider a training sample set {(X1, (1), (2), Y2),..., (X.. Yn)) of size n. Suppose the dimen- sions of feature X; and label Y; are dx and dy, respectively. By aggregating the training sample set, we obtain the feature matrix X E Rdx xn and label matrix Y E gdy
Suppose neural network has L layers. Denote the weight matrix, bias, and activation in the j- th layer respectively by W; E [R4,xd,-1 by E R24, and h R4, xn + R2,x* xn, where dy is the dimension of the output of the j-th layer. Also, for the input matrix X, the output of the j-th layer denoted the y ()) and the output of the j-th layer before the activation is denoted the Y
yt W, w,yb-1) b
yt (W,Y + +,,1,)
(2)
The output of the network is defined follows, y= hr. (W (Wr, W (...hi (WiX + b, 11 ... + b + by, by, Also, define ( X, (4) Y, do dx. and dp dy. In some situations, we to clarify the parameters, as well as y(o) y(), etc.
(3)
Y
This section discusses neural networks with piecewise linear activations. A part of the proof uses two-piece linear activations hg_,e which are defined as follows,
bg (x) [250)___ (2s00842,
where |--1 |s-/ [ is the indicator function.
Remark. Piecewise linear functions are dense in the space of continuous functions. In other words, for any continuous function, we can always find piecewise linear function estimate it with arbitrary small distance.
fontinuuussunctionss
This section uses continuously diffcrentiable loss to evaluate the performance of neural networks. Continuous differentiability is defined as follows.
Definition 1 (Continuously differentiable). We call a function f R" + R continuously differen- tiable with respect to the variable æ if: (1) the function f is differentiable with respect to x; and (2) the gradient V. fzf(x) of the function f is continuous with respect to the variable
3.2 MAIN RESULT
The theorem in this section relies on the following assumptions.
Assumption 1. The training data cannot be fit by linear model.
Assumption 2. All data points are distinct.
Assumption 3. All hidden layers are wider than the output layer. Assumption 4. For the piece-wise linear activations, there exists some turning point that the sum of the slops on the two sides does not equal to O.
To our best knowledge, our assumptions the least restrictive compared with the relevant works in the literature. These assumptions are respectively justified as follows: (1) most real-world datasets
extremely complex and cannot be simply fit using linear models; (2) it is easy guarantee that the data points are distinct by employing data cleansing methods; (3) for regression and many classification tasks, the width of output layer is limited and narrower than the hidden layers; and (4) this assumption is invalid only for activations like f(x) a|z]
Based these four assumptions, we can prove the following theorem.
4

---

Published as a conference paper at ICLR 2020
Theorem 1. Neural networks with arbitrary depth and arbitrary piecewise linear activations (ex- cluding linear functions) have infinitely many spurious local minima under arbitrary continuously differentiable loss whose derivative can equal 0 only when the prediction and label are the same.
In practice, most loss functions are continuously differentiable and the derivative can equal 0 only when the prediction and label are the same, such as squared loss and cross-entropy loss (see Ap- pendix A.I, Lemmas 2 and 3). Squared loss is a standard loss for regression and is defined as the L2 norm of the difference between the ground -rutt label and the prediction as follows.
1 Y; 2
12 YE, v3
(5)
Mcanwhile, cross-entropy loss is used as a standard loss in multiclass classification, which is defined as follows. Here, we treat the softmax function as a part of the loss function.
Y
Lon CY, (Y) -)) Yig log
(6)
Ede k= YI,
One can also remove Assumption 4, if Assumption 3 replaced by the following assumption, which is mildly more restrictive (see detailed proof in pp. 34-37).
Assumption 5. The dimensions of the layers satisfy that:
di 2 dy +
d, 2 dy 11 == 1.
Our result demonstrates that introducing nonlinearities into activations substantially reshapes the loss surface: they bring infinitely many spurious local minima into the loss surface. This result highlights the substantial difference from linear neural networks that all local minima of linear neural networks are equally good, and therefore, they are all global minima (Kawaguchi, 2016; Baldi & Hornik, 1989; Lu & Kawaguchi, 2017; Freeman & Bruna, 2017; Zhou & Liang, 2018; Laurent & von Brecht, 2018; Yun et al., 2018).
Some works have noticed the existence of spurious local minima the loss surfaces of nonlin- ear neural networks, which however has limited applicable domain (Choromanska et al., 2015; Swirszez al., 2016; Safran & Shamir, 2018; Yun al., 2019b). A notable work by Yun et al. (2019b) proves that one-hidden-llyer neural networks with two-piece linear (ReLU-like)) activations for diedeimnnsional regression have infinitely many spurious local minima under squared loss. This work first constructs series of local minima and then prove they are spurious. This idea inspires some of this work. However, our work makes significant and non-trivial development that extends the conditions to arbitrary depth, piecewise linear activations excluding linear functions, and contin- uously differentiable loss.
3.3 PROOF SKELETON
This section presents the skeleton of the proof. Theorem is proved in three stages. We first prove a simplified version of Theorem I and then extend the conditions in the last two stages. The proof is partially inspired by Yun al. (2019b) but the proof in this paper has made nontrivial development and the results are significantly extended.
Yun al. (2019b) and our paper both employ the following strategy: (a) construct a series of local minima based on linear classifier; and (b) construct a new point with smaller empirical risk and thereby we prove that the constructed local minima are spurious. However, due to the differences in the loss function and the output dimensions, the exact constructions of local minima substantially different.
Our extensions from Yun et al. (2019b) are three-fold: (1) From one hidden layer to arbitrary depth: To prove that networks with an arbitrary depth have infinite spurious local minima, we develop a novel strategy that employs transformation operations to force data flow through the same linear parts of the activations, in order to construct the spurious local minima: (2) From squared loss to arbitrary differentiable loss: Yun et al. (2019b) calculate the analytic formations of derivatives of
5

---

Published as a conference paper at ICLR 2020
the loss to construct the local minima and then prove they are spurious. This technique cannot be transplanted to the case of arbitrary differentiable loss functions, because we cannot assume the analytic formation. To prove that the loss surface under an arbitrary differentiable loss has an infinite number of spurious local minima, we employ a new proof technique based on Taylor series and new separation lemma; and (3) From one-dimensional output arbitrar-dimensional output: To prove the loss surface of a neural network with an enpitrary-dimensione output has an infinite number of spurious local minima, and codomain are a matrix space and a vector space, respectively. By contrast, when the output dimension is one, the codomain is only the space of real numbers. Therefore, the extension of the output dimension significantly mounts the difficulty of the whole proof.
need to deal with the calculus of functions whose domain
Stage (1): Neural networks with one hidden layer and two-piece linear activations.
We first prove that nonlinear neural networks with one hidden layer and two-piece linear activation functions (ReLU-like activations) have spurious local minima. The proof in this stage further follows a two-step strategy:
(a) We first construct local minima of the empirical risk R. (see Appendix A.2, Lemma 4). These local minimizers are constructed based on a linear neural network which has the same network size (dimension of weight matrices) and evaluated under the same loss. The design of the hidden layer guarantees that the components of the output (1)) in the hidden layer before the activation are all positive. The activation is thus effectively reduced to a linear function. Therefore, the local geometry around the local minima with respect to the weights W is similar to those of linear neural networks. Further, the design of the output layer guarantees that its output Y is the same as the linear neural network. This construction helps to utilize the results of linear neural networks to solve the problems in nonlinear neural networks.
(b) We then prove that all the constructed local minima in Step (a) are spurious (see Appendix A.2, Theorem 4). Specifically, we assumed by Assumption 1 that the dataset cannot be fit by linear model. Therefore, the gradient V V.R. of the empirical risk R with respect to the prediction Y is not zero. Suppose the i-th row of the gradient V is not zero. Then, we use Taylor series and a preparation lemma (see Appendix A.5, Lemma 7) to construct another point in the parameter space that has smaller empirical risk. Therefore, we prove that the constructed local minima are spurious. Furthermore, the constructions involve some parameters that are randomly picked from a continuous interval. Thus, we constructed infinitely many spurious local minima.
Stage (2) Neural networks with arbitrary hidden layers and two-piece linear activations.
We extend the condition in Stage (1) to any neural network with arbitrary depth and two-piece linear activations. The proof in this stage follows the same two-step strategy but has different implemen- tations:
(a) We first construct series of local minima of the empirical risk R. (see Appendix A.3, Lemma 5). The construction guarantees that every component of the output ( in each layer before the activations is positive, which secure all the input examples flow through the same part of the acti- vations. Thereby, the nonlinear activations are reduced linear functions. Also, our construction guarantees that the output Y of the network is the same as a linear network with the same weight matrix dimensions.
(b) We then prove that the constructed local minima are spurious (see Appendix A.3, Theorem 5). The idea is to find a point in the parameter space that has the same empirical risk R. with the constructed point in Stage (1), Step (b).
Stage (3) Neural networks with arbitrary hidden layer and piecewise linear activations.
We further extend the conditions in Stage (2) to any neural network with arbitrary depth and arbitrary piecewise linear activations. We continue to adapt the two-step strategy in this stage:
(a) We first construct a local minimizer of the empirical risk R based on the results in Stages (1) and (2) (see Appendix A.4, Lemma 6). This construction is based on Stage (2), Step (a). The difference of the construction in this stage is that every linear part in activations can be a finite interval. The constructed weight matrices several uniform scaling and translation operations the outputs

---

Published as a conference paper at ICLR 2020
of hidden layers in order to guarantee that all the input training sample points flow through the same linear parts of the activations. We thereby reduce the nonlinear activations to linear functions, effectively. Also, our construction guarantees that the output y of the neural network equals to that of the corresponding linear neural network.
(b) We then prove that the constructed local minima are spurious (see Appendix A.4). We use the same strategy in Stage (2), Step (b). Some adaptations are implemented for the new conditions.
4 A BIG PICTURE OF THE LOSS SURFACE
This section draws big picture for the loss surfaces of neural networks. Based on recent result by Soudry & Hoffer (2018), we present four profound properties of the loss surface that collectively characterize how the nonlinearities in activations shape the loss surface.
4.1 PRELIMINARIES
The discussions in this section use the following concepts.
Definition (Open ball and open set). The open ball in H centered at x E H and of radius > is defined by B(h, r) = {x: || - hill <. r). A subset A C H of space H. is called open set, if for every point h E A. there exists a positive real r > 0, such that the open ball B(h, r) with center h and radius is in the subset A: B(h,r) C A.
Definition 3 (Interior point and interior). For subset A C H of a space H. point h A is called an interior point of A, if there exists a positive real r > O, such that the open ball B(h, r) with center h and radius is in the subset A: B(hrr) A. The set of all the interior points of the A is called the interior of the set A.
(Limit point, closure, and boundary). For a subset A C H of space H. point h E A called a limit point, if for every r > the open ball rhh with center and radius r contains some point of A: B(h, A Q. The closure A of the set A consists of the union of the set A and all its limit points. The boundary A is defined as the set of points which are in the closure of set A but not in the interior of set A.
Definition
Definition 5 (Multilinear). A function f: X2 X2 - y is called multilinear for arbitrary xt, X. a² x2 E X2. and constants X1, X2. Pi, and μ2, we have
f(A + t22a, ua (222) A +1 +2) A2 22ft2 f(a xz)
Remark. The definition of "multilinear" implies that the domain of any multilinear function f is connective and convex set, such as the smooth and multilinear cells below.
Definition 6 (Equivalence class, and quotient space). Suppose X is linear space. [x]]
(u E X ~ x} is an equivalence class, if there is an equivalent relation on [x)], such that for any b,c E [x]]. we have: (1) reflexivity:
(2) symmetry: if a b, b ~ a; and (3) transitivity: a ~ and b ~ G, a c. The quotient space and quotient map are defined to be X/ ~= HV E X - x) x E X) and + [x], respectively.
4.2 MAIN RESULTS
In this section, the loss surface is defined under convex loss with respect to the prediction Ý of the neural network. Convex loss covers many popular loss functions in practice, such as the squared loss for the regression tasks and many others based on norms. The triangle inequality of the norms secures the convexity of the corresponding loss functions. The convexity of the squared loss is checked in the appendix (see Appendix B, Lemma 8).
We now present four propositions express the loss surfaces of nonlinear neural networks. These propositions give four major properties of the loss surface that collectively draw a big picture for the loss surface.
We first recall a lemma by Soudry & Hoffer (2018). It proves that the loss surfaces of neural networks have smooth and multilinear partitions.
7

---

Published as a conference paper at ICLR 2020
Lemma 1 (Smooth and multilinear partition; cf. Soudry & Hoffer (2018)). The loss surfaces of neural networks of arbitrary depth with piecewise linear functions excluding linear functions are partitioned into multiple smooth and multilinear open cells. while the boundaries nondifferen- tiable.
Based the smooth and multilinear partition, we prove four propositions as follows.
Theorem 2 (Analogous convexity). For one-hidden-layer neural networks with two-piece linear activation for regression under convex loss, within every cell, all local minima are equally good, and also, they are all global minima in the cell.
Theorem (Equivalence classes of local minimum valleys). Suppose all conditions of Theorem hold. Assume the loss function is strictly convex. Then, all local minima in cell are concentrated as a local minimum valley: they are connected with each other by a continuous path and have the same empirical risk. Additionally, all local minima in a cell constitute an equivalence class.
Corollary (Quotient space local minimum valleys). Suppose all conditions of Theorem hold. There might exist some "parallel" local minimum valleys in the equivalence class of local mini- mum valley. They do not appear because of the constraints from the cell boundaries. If we ignore such constraints, all equivalence classes of local minima valleys constitute a quotient space.
Corollary 2 (Linear collapse). The partitioned loss surface collapses to one single smooth and malillinaa cell, when all activations are linear.
4.3 DISCUSSIONS AND PROOF TECHNIQUES
The four propositions collectively characterize how the nonlinearities in activations shape the loss surfaces of neural networks. This section discusses the results and the structure of the proofs. A detailed proof is omitted here and given in Appendix B.
Smooth and multilinear partition. Intuitively, the nonlinearities in the piecewise linear activation functions partition the surface into multiple smooth and multilinear cells. Zhou & Liang (2018); 8); Soudry & Hoffer (2018) highlight the partition of the loss surface. We restate it here to make the picture self-contained. A similar but also markedly different notions recently proposed by Hanin & Rolnick (2019) demonstrate that the input data space is partitioned into multiple linear regions, while our work focuses on the partition in the parameter space.
Every local minimum is globally minimal within a cell. In convex optimization, convexity guar- antees that all the local minima are global minima. This theorem proves that the local minima within a cell are equally good, and also, they are all global minima in the cell. This result is not surpris- ing provided the excellent training performance of deep learning algorithms. However, the proof is technically non-trivial.
Soudry & Hoffer (2018) proved that the local minima in a cell are the same. However, there would be some point near the boundary has a smaller empirical risk and is not locally minimal. Unfortu- nately, the proof by Soudry & Hoffer (2018) cannot exclude this possibility. By contrast, our proof completely solves this problem. Furthermore, our proof holds for any convex loss, including squared loss and cross-entropy loss, but Soudry & Hoffer (2018) only stands for squared loss.
It is challenging to prove. because the proof techniques for the case of linear networks cannot be transplanted here. Technically, linear networks can be expressed by the product of a sequence of weight matrices, which guarantees good geometrical properties. Specifically, the effect of every linear activation function just equivalently multiplying a real constant to the output. However, the loss surface within a cell of nonlinear neural network does not have this property. Below is the skeleton of our proof.
We first prove that the empirical risk R. is a convex function within every cell with respect to a variable W which is calculated from the weights W. Therefore, all local minima of the empirical risk with respect to W are also globally optimal the cell. Every cell corresponds to a specific series of linear parts of the activations. Therefore, in any fixed cell, the activation h4 ha..* can be expressed by the slopes of the corresponding linear parts as the following equations,
R(W,, W2) = n Σ 1 (y., W W2h(Wiaa) =
Σ I (Vc. Wydiag (A.,) W1x;),
(7)
8

---

Published as a conference paper at ICLR 2020
where A. is the i-th column of matrix
h ((11)1..11
11 1a_ ((W1)1,
A
14, .44 (WW)),
h2_,, (Wi)d,,
Matrix A is constituted by collecting the slopes of the activation h at every point (W1 ay...
Different elements of the matrix A can be multiplied either one of 8+- Therefore, we cannot use a single constant to express the effect of this activation, and thus, even within the cell, a nonlinear network cannot be expressed the product of sequence of weight matrices. This difference ensures that the proof's of deep linear neural networks cannot be transplanted here.
Then, we prove that (see p. 40)
Widiag (A.,) Wi2;
Applying eq. (8) to eq. (7), the empirical risk R equals to formulation similar to the linear neural networks,
R Σ 1
(9)
Afterwards, define W, (daa((2)) and then straighten the matrix Wi vector W,
W- = ((W)),
(Wi),.))
Define Q (W1, W2) W, and also define,
X = (A., æ
A, 8 xn).
We can prove the following equations (see p. 41),
(AT, W1
AT Wi.,) =WX.
Applying eq. (9), the empirical risk is transferred to a convex function as follows,
R (A..) War:)
1 Σ Mvv Wx)).
We then prove that the local optimality mapped to the variable W. Specifically, the local minima of the empirical risk R with respect to the weight W are also the local minima with respect to the variable W. The maintenance of optimality not surprising but the proof is technically non-trivial (see detailed proof in pp. 42-43).
empirical risk R is maintained when the weights W are
classes and quotient space local minimum valleys. The constructed mapping Q is quotient map. Under the setting in the previous property, all local minima a cell is an equivalence class; they are concentrated as a local minimum valley. However, there might exist some "parallel" local minimum valley the equivalence class, which do not appear because of the constraints from the cell boundaries. Further for neural networks of arbitrary depth, we also constructed a local minimum valley (the spurious local minima constructed in Section 3). This result explains the property of mode connectivity that the minima found by gradient-basse methods are connected by path in the parameter space with almost constant empirical risk, which is proposed two empirical works (Garipov et al., 201 8; Draxler et al., 2018). A recent theoretical work (Kuditipudi et al., 2019) proves that dropout stability and noise stability guarantee the mode connectivity.
Equivalence
Linear collapse. Our theories also cover the case of linear neural networks. Linear neural networks do not have any nonlinearity in their activations. Correspondingly, the loss surface does not have any non-differentiaale boundaries. In our theories, when there is no nonlinearity in the activations, the partitioned loss surface collapses to a single smooth, multilinear cell. All local minima wherein equally good, and also, they are all global minima follows. This result unites the existing results on linear neural networks (Kawaguchi, 2016; Baldi & Homii,, 1989; Lu & Kawaguchi, 2017; Freeman & Bruna, 2017; Zhou & Liang, 2018; Laurent & von Brecht, 2018; Yun et al., 2018).

---

Published as a conference paper at ICLR 2020
5 CONCLUSION AND FUTURE DIRECTIONS
This paper reports that the nonlinearities in activations substantially shape the loss surfaces of neural networks. First, we prove that neural networks have infinitely many spurious local minima which are in contrast to the circumstance of linear neural networks. This result stands for any neural network with arbitrary hidden layers and arbitrary piecewise linear activations (excluding linear functions) under many popular loss functions in practice (e.g., squared loss and cross-entrope loss). This result significantly extends the conditions of the relevant results and has the least restrictive assumptions that cover most practical circumstances: (1) the training data is not linearly separable; (2) the training sample points are distinct; (3) all hidden layers are wider than the output layer; and (4) there exists some turning point in the piece-wise linear activation that the sum of the slops on the two sides does not equal to O. Second, based on a recent result that the loss surface has a smooth and multilinear partition, we draw big picture of the loss surface from the following aspects: (1) local minima in any cell are equally good, and also, they are all global minima in the cell; (2) all local minima in one cell constitute an equivalence class and are concentrated as a local minimum valley; and (3) the loss surface collapses to one single cell when all activations are linear functions, which explains the results of linear neural networks. The first and second properties are rigorously proved for any one- hidden-layer nonlinear neural networks with two-piece linear (ReLU-like) activations for regression tasks under convex/strictly convex loss without any other assumption.
Theoretically understanding deep learning is of vital importance to both academia and industry. A major barrier recognized by the whole community is that deep neural networks' loss surfaces are extremely non-convex and even non-smooth. Such non-convexity and non-smoothness make the analysis of the optimization and generalization properties prohibitively difficult. A natural idea is to bypass the geometrical properties and then approach theoretical explanation. We argue that such "intimidating" geometrical properties are exactly the major factors that shape the properties of deep neural networks, and also the key to explaining deep learning. We propose to explore the magic of deep learning from the geometrical structures of its loss surface. Future directions towards fully understanding deep learning are summarized follows,
Investigate the (potential) equivalence classes and quotient space of local minimum valleys for deep neural networks. This paper suggests degenerate nature of the large amounts of local minima: all the local minima within one cell constitute an equivalence class. We construct a quotient map for one-hidden-layer neural networks with two-piece activations for regression. Whether deep neural networks have similar properties remains an open problem. Understanding the quotient space would be major step of understanding the approximation, optimization, and generalization of deep learning.
Explore the sophisticated geometry of local minimum valleys. The quotient space of local minima suggests strategy that treats every local minimum valley as a whole. How- ever, the sophisticated local geometrical properties around the local minimum valleys are still premature, such as the sharpness/fatness of the local minima, the potential categoriza- tion of the local minimum valley according to their performance, and the volumes of the local minima valleys from different categories.
Tackle the optimization and generalization problems of deep learning. Empirical re- sults have overwhelmingly suggested that deep learning has excellent optimization and generalization capabilities, which is, however, beyond the current theoretical understand- ing: (1) one can employ stochastic convex optimization methods (such as SGD) to min- imize the extremely non-convex and non-smooth loss function in deep learning, which is expected to be NP-hard but practically solved by computationally cheap optimization methods; and (2)
neural networks can generalize well in many tasks, which is beyond the expectation of most current theoretical frameworks based on hypoth- esis complexity and the variants. The sophisticated geometrical expression, if fortunately, we possess in the future, would be compelling push tackle the generalization and opti- mization muses of deep learning.
ACKNOWLEDGMENTS
This work was supported by Australian Research Council Project 1L-170100117 The authors sin- cerely appreciate Micah Goldblum and the anonymous reviewers for their constructive comments.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li. and Yingyu Liang, Learning and generalization in overparameter- ized neural networks, going beyond two layers. In Advances in Neural Information Processing Systems, 2019a.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. International Conference on Machine Learning, 2019b.
Marcin Andrychowicz, Misha Denil, Sergio Gomez, Matthew W Hoffman, David Pfau, Tom Schaul, Brendan Shillingford, and Nando De Freitas. Learning to learn by gradient descent by gradient descent. In Advances in Neural Information Processing Systems, 2016.
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparamcterization In International Conference on Machine Learning, 2018.
Pierre Baldi and Kurt Hornik. Neural networks and principal component analysis: Learning from examples without local minima. Neural Networks, 2(1):53-58, 1989.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for convnet with gaussian inputs. In International Conference on Machine Learning, 2017.
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai parameterized networks that provably generalize on linearly separable data. In International Conference Learning Representations, 2018.
SGD learns over-
Lénaic Chizat and Francis Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. In Advances in Neural Information Processing Systems.
Anna Choromanska, Mikael Henaff, Michael Mathicu, Gérard Ben Arous, and Yann LeCun. The loss surfaces of multilayer networks. In International Conference Artificial Intelligence and Statistics, 2015.
Felix Draxler, Kambis Veschgini. Manfred Salmhofer, and Fred Hamprecht. Essentially no barriers in neural network energy landscape. International Conference on Machine Learning. 2018.
Simon Du, Jason D Lee, Haochuan Li, Liwei Wang. and Xiyu Zhai Gradient descent finds global minima of deep neural networks. In International Conference Machine Learning, 2018a.
Simon S Du, Jason D Lee, Yuandong Tian, Barnabas Poczos, and Aarti Singh. Gradient descent learns one-hidden-layer cnn: Don't t be afraid of spurious local minima. In International Confer- ence on Machine Learning. 2018b.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference Learning Representations, 2019.
C Daniel Freeman and Joan Bruna. Topology and geometry of half-rectified network optimization. In International Conference on Learning Representations, 2017.
Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry P Vetrov, and Andrew G Wilson. Loss surfaces, mode connectivity, and fast ensembling of dnns. In Advances in Neural Information Processing Systems, 2018
Micah Goldblum, Jonas Geiping, Avi Schwarzschild, Michael Moeller, and Tom Goldstein. Truth or backpropaganda? an empirical investigation deep learning theory. In International Conference on Learning Representations, 2020.
Benjamin D. Haeffele and Rene Vidal. Global optimality in neural network training. In IEEE
Conference on Computer Vision and Pattern Recognition, July 2017.
Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. In International Conference Machine Learning, 2019.
11

---

Published as a conference paper at ICLR 2020
Fengxiang He, Tongliang Liu, and Dacheng Tao. Control batch size and learning rate to generalize well: Theoretical and empirical evidence. In Advances in Neural Information Processing Systems, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In IEEE Conference on Computer Vision and Pattern Recognition, 2016.
Kenji Kawaguchi. Deep learning without poor local minima. In Advances in Neural Information Processing Systems, 2016.
Kenji Kawaguchi and Leslie Pack Kaelbling, Elimination of all bad local minima in deep learning. In International Conference on Artificial Intelligence and Statistics, 2020.
Rohith Kuditipudi, Xiang Wang. Holden Lee, Yi Zhang, Zhiyuan Li, Wei Hu, Sanjecv Arora, and Rong Ge. Explaining landscape connectivity of low-cost solutions for multilayer nets. In Ad- vances Neural Information Processing Systems, 2019.
Thomas Laurent and James von Brecht. The multilinear structure of relu networks. In International Conference on Machine Learning. 2018.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521 521(7553):436, 2015.
Dawei Li, Tian Ding, and Ruoyu Sun. Over-parameterizee deep neural networks have no strict local minima for any continuous activations. arXiv preprint
2018.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent structured data. In Advances in Neural Information Processing Systems 31. 2018.
Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with relu activation. In Advances in Neural Information Processing Systems 30. 2017.
Shiyu Liang, Ruoyu Sun, Yixuan Li, and Rayadurgam Srikant. Understanding the loss surface of neural networks for binary classification. International Conference on Machine Learning. 2018.
Geert Litjens, Thijs Kooi, Babak Ehteshami Bejnordi, Arnaud Arindra Adiyoso Setio, Francesco Ciompi, Mohsen Ghafoorian, Jeroen Awm Van Der Laak, Bram Van Ginneken, and Clara I Sánchez. survey on deep learning in medical image analysis. Medical Image Analysis, 42: 60-88, 2017.
Haihao Lu and Kenji Kawaguchi. Depth creates no bad local minima. 170.00700..88800 2017.
arXiv preprint
Song Mei, Yu Bai, Andrea Montanari, et al. The landscape of empirical risk for nonconvex losses. The Annals of Statistics, 46(6A))2747-2744 2018.
Quynh Nguyen. On connected sublevel sets in deep learning. In International Conference on Machine Learning, 2019.
Quynh Nguyen and Matthias Hein. Optimization landscape and expressivity of deep enns. In International Conference on Machine Learning, 2018.
Quynh Nguyen, Mahesh Chandra Mukkamala, and Matthias Hein. On the loss landscape of class of deep neural networks with no bad local valleys. International Conference on Learning Representations, 2019.
Samet Oymak and Mahdi Soltanolkotabi. Overparameterized nonlinear learning: Gradient descent takes the shortest path? In International Conference on Machine Learning, 2019.
Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer relu neural networks. In International Conference on Machine Learning, 2018.
Levent Sagun, Léon Bottou, and Yann LeCun. Singularity of the hessian in deep learning. arXiv preprint ar 161 007476, 2016.
12

---

Published as a conference paper at ICLR 2020
Levent Sagun, Utku Evci, V Ugur Guney. Yann Dauphin, and Leon Bottou. Empirical analysis of the hessian of over-parametrized neural networks. In International Conference on Learning Representations Workshop, 2018.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 448,, 2016.
Mahdi Soltanolkotabi. Learning relus via gradient descent. In Advances Neural Information Processing Systems 30. 2017.
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of over-parameterizee shallow neural networks. IEEE Transactions on Information Theory, 65(2):742-769, 2018.
Daniel Soudry and Elad Hoffer. Exponentially vanishing sub-optimal local minima in multilayer neural networks. In International Conference on Learning Representations Workshop, 2018.
Grzegorz Swirszez, Wojeiech Marian Czarnecki, and Razvan Pascanu. Local minima in training of deep networks. arXiv preprint 161 1:063 10, 2016.
Yuandong Tian. An analytical formula of population gradient for two-layered relu network and its applications in convergence and critical point analysis. In International Conference on Machine Learning. 2017.
Gang Wang, Georgios B Giannakis, and Jie Chen. Learning relu networks linearly separable data: Algorithm, optimality, and generalization. IEEE Transactions on Signal Processing, 67(9): 2357-2370, 2019.
Ian H Witten, Eibe Frank, Mark A Hall, and Christopher J Pal. Data Mining: Practical machine learning tools and techniques. Morgan Kaufmann, 2016.
Chenwei Wu, Jiajun Luo, and Jason D Lee. No spurious local minima in two hidden unit relu network. International Conference on Learning Representation Workshop, 2018
Bo Xie, Yingyu Liang, and Le Song. Diverse neural network learns true target functions. In Inter- national Conference Artificial Intelligence and Statistics, 2017.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Global optimality conditions for deep neural networks. In International Conference on Learning Representations, 2018.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Efficiently testing local optimality and escaping saddles for reLU networks. In International Conference on Leurning Representations, 2019a.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small nonlinearities in activation functions create bad local minima in neural networks. In International Conference on Learning Representations, 2019b.
Hongyang Zhang, Junru Shao, and Ruslan Salakhutdinov. Deep neural networks with multi-branch architectures are intrinsically less non-convex. In International Conference on Artificial Intelli- gence and Statistics, 2019a.
Xiao Zhang, Yaodong Yu, Lingxiao Wang, and Quanquan Gu. Learning one-hidden-layer relu net- works via gradient descent. In International Conference on Artificial Intelligence and Statistics, 2019b.
Kai Zhong, Zhao Song, Prateck Jain, Peter L Bartlett, and Inderjit S Dhillon. Recovery guarantees for one-hidden-layer neural networks. In International Conference on Machine Learning, 2017.
Pan Zhou and Jiashi Feng. Empirical risk landscape analysis for understanding deep neural net- works. In International Conference on Learning Representations, 2018.
Yi Zhou and Yingbin Liang. Critical points of neural networks: Analytical forms and landscape properties. In International Conference on Learning Representations, 2018
13

---

Published as a conference paper at ICLR 2020
Yi Zhou, Junjie Yang, Huishuai Zhang, Yingbin Liang, and Vahid Tarokh. SGD converges to global minimum in deep learning via star-convex path. In International Conference on Learning Repre- sentations, 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. Machine Learning, 2019.
14

---

Published as a conference paper at ICLR 2020
A PROOF OF THEOREM
This appendix gives a detailed proof of Theorem omitted from the main text. It follows the skeleton presented in Section 3.3.
A.1 SQUARED LOSS AND CROSS-ENTROPY LOSS
We first check whether squared loss and cross-entropy loss are covered by the requirements of Theorem 1.
Lemma 2. The squared loss (defined by eq. 5) is continuously differentiable with respect to the prediction of the model, whose gradient of loss equal zero when the prediction and the label are different.
Proof. Apparently, the squared loss differentiable with respect to Y. Specifically, the gradient with respect to Y as follows,
vr felr-Pi 81 22 -x-
which is continuous with respect Y.
Also, when the prediction Y does not equals to the label Y, we have
y & 1| #
The proof is completed.
Lemma 3. The cress-entropy loss eq. (6) is continuously differentiable with respect to the prediction of the model, whose gradient of loss equal to zero when the prediction and the label are different. Also, we assume that the ground-truth label is a one-hot vector.
Proof. For any i E [1 n]. the cross-entropy loss is differentiable with respect to Y,. The j-th component of the gradient with respect to the prediction Y, is as follows.
Paa Ddy Nore
a
Yk,i log
dy
k=
Ykus
Vj
(10)
oÝ,,
which is continuous with respect to Y, So, the cross-entropy loss is continuously differentiable with respect to y,
Additionally, if the gradient (eq. (10)) is zero, we have the following equations,
Σ Yks
81.
Yj
Su.t 0, j 1,
k=1
Rewrite it into the matrix form, have
dy
Ys,
Y1.
Y1,
-Y,s
chi
dy
-2,
Σ Yk.s
Y2,1
-Y2,
:
dy
Vay
Σ Yk.i - Vay
i=1
15

---

Published as a conference paper at ICLR 2020
Since Σ
Yk = 1, we can easily check the rank of the left matrix is dy 1. So the dimension of the solution space is one. Meanwhile, we have
A=1
dy
Σ
11,
-Y1,i
-Yi,
Y1,
2,4
Yu.i
Y2i
-Y2,i
Y2,
k=
0.
Yay
.ay
Yay,
Σ
Yk,s
Yay
Therefore, 0 # evka XYE,, for some À E R. which contradicts the assumption that some of the components of Y is 0 (Y, is a one-hot vector).
The proof is completed.
A.2 STAGE (I)
In Stage (1), we prove that deep neural networks with one hidden layer, two-piece linear activation h4 and multi-dimensional outputs have infinite spurious local minima.
This stage is organized as follows: (a) we construct a local minimizer by Lemma 4; and (b) we prove that the local minimizer is spurious in Theorem 4 by constructing set of parameters with smaller empirical risk.
Without loss of generality, assume that 8+ * O. Otherwise, suppose that 8 0. From the definition of ReLUU-like activation (eq. (4)), we have 8 f 0. Since
hg (Ir) = h
the output of the neural network with parameters { / [b:] [0: }
and activation hg_.., equals
to that of the neural network with parameters [ [b1 and activation --. -- where W! = W, = -b,, 1,2, ... L and W7 WL, b1 by. Since {wall [b,][1]] }
[W: } is an one-to-one map, is equivalent consider either the two networks, with h-e4.-e_ (x) has non-zero slope when > 0.
Step (a). Construet local minima the loss surface.
Lemma 4, Suppose that W a local minimizer of
( Y,
xz [Tt])
f(W)
(11)
1=1
Under Assumption 3, any one-hidden-layer neural network has local minimum at
W
W.=
[[xxx]
b1
mlay
(12)
0 (di (il-dy)xi Xxxx
1 dr-
and
]. b2 1
W₂
Idy
Ody ((dx
(13)
84
where Wi and bn respectively the weight matrix and the bias of the first layer, W, and by respectively the weight matrix and the bias of the second layer, and n is a negative constant with absolute value sufficiently large such that
W 1l 1s 0.
(14)
where is element-wise.
Also, the loss in this lemma is continuously differentiable loss whose gradient does not equals to when the prediction is not the as the ground-truth label.
16

---

Published as a conference paper at ICLR 2020
Proof. We show that the empirical risk is higher the neiborhood of to prove that
W;
1²
[8g]
order
i=1 im1
W
is a local minimizer.
i=1
The output of the first layer before the activation is
W - ny 17 6 W, x + b,
-1,1, -dy 1"
Because 17 is a negative constant with absolute value sufficiently large such that eq. (27)) holds, the output above positive (element-wise) -wise),,wis),, the output of the neural network with parameters (Wa, W2, b, b2)
y W2h, .t (Wix x + b11%) 621
W2 (wix + 611%) + 621
=8 1 lay
Ody x
]
WX nl 17 -111d dy 1
+ m dy 1
=W X,
where X is defined as Therefore, the empirical risk R in terms of parameters {W1, W2, b1, b2 is
X X
(15)
1
R (Wa, W2, W2,b1, b1, = Yi, ( =
n
Yú, W
xx = s(W).
i=1
Then, we introduce sufficiently small disturbance
{lówa] [dw] into the parameters
W 1=1 [.].) When the disturbance is sufficiently small, all components of the output
of the first layer remain positive. Therefore, the output after the disturbance is
4 ([Wi+ 5ws]
ow:] r= [b, + 5ud i=1
W22 + ówz) h ((Ri + 6w1
X + (i 5b1 12 + (b2 + 862 1st
( W2 + ówz) st ((wi+ dwi) ) X + (b, + Sm 1nj + (62 + 612 1s
=m0 ((1i 5w1) X + (b + +da) 17' + Wodw1 + 8+ W2dn 1"t + 862 17
+ W28+ (W,X + b 11)) + 122
-(s+ōw2 (Wi + +dwI) ) + 8 W2dw1)
X + (s. W2d0r + 8b2 + 8 (b, + dos) 0o1)) 1
+ Wahe (WiX + 1,) + 12
X
-(W +6)
where eq. (+) is because all components of (wi + (Wi+ōwr)) x + (b4 + 501) 1% are positive, and is
defined as the following matrix
8+ (W2dww + :w Wi, + owzdwi)
W2dmi + ōbz + s..w2 (b, + 5m )
17

---

Published as a conference paper at ICLR 2020
Therefore, the empirical risk R with respect to
+ dw:
12
[;; + dbi
2 is
im1
i=1
R (Ii: +ow,+ owl
1 ]=] i=1
81 + ôbi
2
1
Yi, ( + +5) x) +5)x)
i=1
n1 1=1
1
n
[3
Σ
Yi W + +5)
[1]
n2
S(W + 6).
ô approaches zero when the disturbances {ów1, ow2, 861, d12} approach zero (element-wise). Since W is the local minimizer of ((W), we have
R ([wl i=1 [.
2 ) S(W) S S(W +8) (1 6ws ]w:] 1=1 [6g + dod 1² |=)) (16)
Because the disturbances (ōw1, ,w 9a1 d1a} are arbitrary, eq. (16) demonstrates that a local minimizer.
[w: [ [6.
The proof is completed.
Step (b). Prove the constructed local minima are spurious.
Theorem 4. Under the same conditions of Lemma 4 and Assumptions 1, 2, and 4, the constructed spurious local minima in Lemma are spurious.
Proof. The minimizer W is the solution of the following equation
WwJ(W) = 0.
Specifically, we have
0ʃ (
0, ie {1. .......d))) 1..,.,,dxh
aW.j
Applying the definition of f(W) (eq. (11)),
0f W
Vg.l
Yi, W
x
Eud
Vg.
Yo, W
a I))
(H))
x
OWkj
1
where y, = W [z Yú, w
[x;]
V
[1]
E IRR Ixddy
Since k. j are arbitrary in {1,.... dy } and
(1.....dd dx). respectively, we have
V
1m] 0,
(17)
where
V v-
[
21 1 (=)))) Vi, W
(V Yn W
Inn
)"]"
1
We then define y WX. Applying Assumption 1, we have
Y --Y (wx-x) 0,
Thus, there exists some h-th row of & Y that does not equal to 0.
18

---

Published as a conference paper at ICLR 2020
We can rearrange the rows of W and Y simultaneously, while W is maintained as the local mini- mizer of fW) and f f(W) invariant'. Without loss of generality, assume & = 1 (k is the index of Y1,, in Lemma 7. There exists non-empty separation I = [1 and J = [2 + 1 n| of S (1,2, ... .n and vector 3 Rex, such that
the row). Set V1, and
(1.1) for any positive constant small enough, and E I.j J, J,Y,, az"x, <Vis aB zzj
(1.2) EiEr V1,1 + 0. Define
min (Yi, -33 - (FE. a3 xx)²a:)))) m:))
1h = F1 - aB xv + 2 iE((4
Applying (1.1), for any i E
V1, a.3 x; 7
= (fi.i -afet vj Y2 13fxrr)
1 ( min (E.(V_).....)))
(Fi, a3txI. (Fr. aB" xv)
<0,
while for any j E J.
P1. a3 2₁- - 111 >
= (FlJ - aB Ij - V1.1 + a1 21)
( min
(
(Vi, - a3 (P - a3 xx)
2 (E(("+)....)))
as ass=2z)
(Fi. - ai3 z1r)
22
min [E(((+I.....))
>0.
Define y R which satisfies
min 1 + a (I: Bi), I' <1111
8141
hl
a
1' = 8111
where 8411 is defined in Lemma 7.
We argue that
1 min
(f1.- Bi.--33T - (Yi. 1i,v-afk -a3Txx) xv) ) - -hl > 0.
-
(18)
2
(I..._)....)))
When 1' = 81+1, eq. (58) stands. Also,
lim 7 =0, 0, a-10-
lim a
min (E(("+).....) (Fi. - a.3 x3)
- a,3 xr mn)) (Vi.--afh
min
V1, - Fr, > 0.
se(++1,....))
Therefore, we get eq. (18) when a is small enough.
When l' < S141. eq. (57) stands. Therefore,
1 1 min |r|
(Pi. - o33 -Vi a xx
2 2
which apparently leads to eq. (18).
is also the function in term of Y
19

---

Published as a conference paper at ICLR 2020
Therefore, for any I, we have that
1 aB I;
111 + |y|
(ie( (f1.1- 2i) -P (33T)
xx )) + ll
5 min
<0,
while for any j E J
Yi.
aB"xz Ij 111 - -hi
(Y aB 2:) -P -BB xx) )) lml
min ie((+llmm))
>0.
Furthermore, define (2 < i S dy) negative reals with absolute value sufficiently large, such that for any E [2: dy] and any E m). Y 17 0.
Now construct point in the parameter space whose empirical risk is smaller than the proposed local minimum in Lemma as follows
W1.[1xxx] - 0,37
Wiippdx] + aB W2(110xl
Wi=
(19)
Wdy
0 1dd-dy-- -1xxxx
W1.dxx+1] 771 +
+1 + 7111 +
W2 W21dx+11 7/2
b
(20)
W ddy,|dx+11 Ddy
[dx
( -oh-dy-11e
0
0
#4
W₂
1
0
(21)
and
7/1
7/2
b2
(22)
Ady
where W, and 6; the weight matrix and the bias of the i-th layer, respectively.
20

---

Published as a conference paper at ICLR 2020
After some calculations, the network output of the first layer before the activation in terms of W
0/
is
i=1
1=1
W1 - a
+ + W1, + x 1 + +
W2. 1/21"
y = WiX x +b,1
;
Wdy X ndy 17 0 (d) -dy 1)
Therefore, the output of the whole neural network
y Wehe.st .t
[WiX + b11%) + b21
W 8 -aag X 111 1 + 7
- WW,, X + o.3 X + m 1 + +71
W2, - 1
Weh
+ b T.
Way X - Bdy 17
(di 11
Specifically, j S v'
g: (1vx)² )= [b]]
2 [T]==1) 1.j
=W,,
0.3TT Fj 111 +
1
=Pis a.
Ij 111 + < 0,
F(a) ([v)) 1=1
[b]] [=]
W1,
+ a 2 + m +7 +
2,j
Vi + a.3 + +7>
[w:]]
2
Therefore, (1,j)-th component of y
is
i=1
i=1
y ((w1] [ 2 [6.] 2
1=1" 1== 15
Wi,X - a.3²x X - m + 1 -W,,X X + a:3 X + 7 n + 1
W2,X - 1/2
(440=' 84t0 .0... .0) hs hs
Way, X nd T
n
0₂ ddy 1
-9
+ 17
ha ss 1813
- aB8 x. - 111 + +7)
lis ,01 (-81.s + a4 2j + m + 7)
84 + 8_
8_ +
+ ?71
(Vi, a x.j m71 7)
8t
(-82, a.5 x, + m +7)
84 +
st +s_ s_
+ 171
-Y1, -o,3T
x. + 8_ 3+ 7,
(23)
84 + S_
21

---

Published as a conference paper at ICLR 2020
Similarly, when j > 1', the (1, j'th component is
y
W
05 2
im11 )
im1
1.j
8+
(M1. - aBB 2jj
- + +7)
s- +
(-81,3 a3 Tj + + + +m
84 +
-Y aBt xs + 84
(24)
84 + 8-
and
y
W i=1
8+
+Y 11.) "i Yiij i2 2.
(25)
13
84
[w:]]
2
Thus, the empirical risk of the neural network with parameters
0
i=1
i=
R
W
1
[8,
1
1-1
i=1
Yr, W/
(Wiz; + b117)) + by1"")
n
m
1 Wr,W w
[x:]
1 V (x (x::Wi W
[x;] (1:]) ( W/2
(Wizs+ (Wixs+ +b,1 + b2 w
[T:]
[xq]]
)
W/ (Wi=; b1177) + b22 - w [z
1 |)
(26)
Applying eqs. (23), (24), and (25), we have
[x1]]
We W12; bi) + b2 -b2- 1V
V
Yi, W
[1]
1
(-,3--
Tj +
- 7)+ + Σ (-.3
84 8 8-
x3
84 8
84 + 8
84 + 8_
84 s Vi,s
27
8 + 8
where eq. (+) is because
a.f x, 8_ 84
7,
j=
84 + s__
We (Wix; + +bi +bb W
[x;]
1
a D.
8_ 8
j 1=1,i>1
84 +
j22
Furthermore, note that a O(7) (from the definition of 7). We have
Ni' (Wi:; + bi) bo W [11 ))
x2
W7 [Wi;; + bn)) + by W [z;] 2
Σ
Σ
=0(>)-
22

---

Published as a conference paper at ICLR 2020
Let a be sufficiently small while sgn(7) = -ggn
Σ
Vi,
We have
$475-
1, W2
W100 + b1) (2))
E1
1
Yi, W [z
[1]
i=1
8 8
= 27
V1, -(7)
84
1=1
(++)
< 0,
where inequality (**) comes from (1.2) (see p. 18).
2 [b]=]]
From Lemma 4, there exists a local minimizer
[w
with empirical risk that equals
to S(W). Meanwhile, we just construct a point the parameter space with empirical risk smaller than f(W).
? 1=1
Therefore,
W
[6 1=1
spurious local minimum.
The proof is completed.
A.3 STAGE (2)
Stage (2) proves that neural networks with arbitrary hidden layers and two-piece linear activation ha_ have spurious local minima. Here, still assume 54 of O. We have justified this assumption in Stage (1).
This stage is organized similarly with Stage (I): (a) Lemma 5 constructs a local minimum; and (b) Theorem proves the minimum is spurious.
Step (a). Construct local minima of the loss surface.
Lemma 5. Suppose that all the conditions of Lemma 4 hold, while the neural network has L
hidden layers. Then, this network has local minimum at
W
1.
W
[[[:xx]
81
x,xx +1 -1/
O(ds ddy xxxx
1 dy
d
W =
Eg +
Σ
Eg 8/ = 0 2,3, --, --1,
8+ j=1
8+ -=
and
WL
=
1 L
Oay x ((de-i--dy ]. B/2 m/yay
where Wi and 8, are the weight matrix and the bias of the i-th layer, respectively, and rj is a negative constant with absolute value sufficiently large such that
WX my1d 17 0.
(27)
where > is element-wise.
Proof. Recall the discussion in Lemma that all components of WiX X + b 17 are positive. Specif- ically,
Y 1y 1T
W,X - 6,17
17 dy T
where ÿ is defined in Lemma 4.
23

---

Published as a conference paper at ICLR 2020
[w [w:]]_] i=1
[61] [6]]_]] the
Similar to the discussions in Lemma 4, when the parameters equal to output of the first layer before the activation function is
Y 17 1y 1
y = = 1
1//d dy 1
and
y - 1l n > 0,
(28)
1 1 >0. 0.
(29)
Here is defined element-wist wise.
After the activation function, the output of the first layer is
- ry 1
(()) he_.._ (Wix + (1 s_ (W,x +, s_
11 - 17
We prove by induction that for all i E [1 L 1] that
(1) > 0 element-wist wise,
(30)
Ý 11 1
y( 8+
(31)
-1/ dy 17
Suppose that for 1 s k < L (x) is positive (element-wise and
Y 1d 12
(R) 8+
- dy I
Then the output of the (I: + 1)-th layer before the activation
( WK W y (R)
8 1
dy Ejj +
dR+1
V ly dr 17"
Σ
Bg(dr+1)
84
j=1
j=dy+1
11 du dy 1.
lyy 1
d711441-d 17
Applying eqs. (28) and (29), we have
Y 1/ 1s
(k+1)
>0,
17 ddy 17
where > is defined element-wisg wise. Therefore,
ÿ. - I T n
y(++1) h, (v(tH)) s+ ((++1)
1 dy 12
We thereby prove eqs. (30) and (31). Therefore, (L) can be calculated as
ÿ = (4) = W (L-1)) + 1/
Y 1jldy 17
Lay 04yxide-1-dr)
+ mld 1s
17 -. 1
V.
(32)
24

---

Published as a conference paper at ICLR 2020
Then, we show the empirical risk is higher around [W:]] L
2 i=1 [8]] [8]]]]]]
order to prove that
{ [[m:] i=1 [8]]
L
is a local minimizer.
==1]
Let { {[w:+ 8iri
[6
L i=1
+ 8/
be point in the parameter space which is close enough to the Since the disturbances owr and 8y are both close to (element-wise),
i=1
L [[m:]]
point
i=1
i=1
all components of ()())
([w + ow |_m i=1
[6%++ +6, remains positive. Therefore, the output
{ { + oir 16 1=1
[6 + %% is
of the neural network in terms of parameters
Ý ([ig +ow++ i=1 [6; +0/5
] i=1
=(W% + 1 11100- (.. (...hs (WV (8/ + 8wr1) x + (8/ (8/+))))))) 17 11)..) ...)
+ (bz, 8/1.) 1"
-(W2 + +8w1)s.
(...8+ (WW(+8w1) x (81 + 8/11 17) ...)
+ (B,. + 8.1)) 1
= =M,X + Mz1
[6]] i=1
and { (1ordl 18 through
where M1 and M2 can be obtained from several multiplication and summation operations..
i=1
Rewrite the output as
X -
Mi M2 [M
M2]
Therefore, the empirical risk R before and after the disturbance can be expressed as f(W) and ff ([M, M2]). respectively.
When the disturbances (1 (8bel approach (element-wise), [M1
Mg] approaches W.
Therefore, when { 1 15% } are all small enough, we have
R
([iV'++ + 6wr:] 1-1
oiv:]=
b% - 566
I.
i=1
= =[[M M2))
z((W)
- [w::]]
1= [wt:]]_
[6] (
(33)
Since
[w 8ws]
} are arbitrary within sufficiently small neighbour of 1= eq. (33) yields that { [[::]²
1 1=1
0 8/c ]
[w:]] m
1=1 8
is local minimizer.
Step (b). Prove the constructed local minima spurious.
"innce the exact form of M, and M2 are needed, we omit the exact formulations here.
25

---

Published as a conference paper at ICLR 2020
Theorem's 5. Under the same conditions of Lemma 5 and Assumptions 1, 2, and 4, the constructed spurious local minima in Lemma are spurious.
Proof. We first construct the weight matrix and bias of the i-th layer as follows.
W W1, b1 b1,
W₂
by
W2
8/2 Aldz +
( (yd2-dy)xdd {xdi
(dy=-dy)x11
dy
W
Eagir by 0 (i 3, 4, ..., L-
8+ iml
and
dy
W7 = 8+
Eiss. b/ = -Aldy
where Wi, W2. by and by are defined by eqs. (19), (20), (21), and (22), respectively, and À is sufficiently large positive real such that
y ([w))
2
6e 2 1=1
A1dd, 0,
(34)
i=1
where defined element- wise.
We argue that { [
[ -
corresponds to a smaller empirical risk than f(W) which
defined in Lemma 4.
First, Theorem 4 has proved that the point { [w, W2, by b2) corresponds to a smaller empirical risk
than S(W).
We prove by induction that for any i E {3, 4, ..., Io 1}.
W i=1
0. element-wise,
(35)
y [
+ Ald 17
y
[ 1 i=
b3 )=11
i=1
(36)
Odde-dy))
Apparently the output of the first layer before the activation is
p / -_ [6]] (
W - wix 8(0) ([wp²²
i=1
1=11
Therefore, the output of the first layer after the activation is
y(1) (w:]] L
[6 [=)]
5(1)
177
i=1
- +
(1)
[w:
b
1=1
[5 2
=1
i=1
i=1
26

---

Published as a conference paper at ICLR 2020
Thus, the output of the second layer before the activation is
(())) (ww) [0]
1= wyy(1)
1.
1. ([wz1)
i=1 [6 1=1
6/17%
W2
y(u))
[WT]]] i=1
[86]
82
1
(d2 (od-dd)xxc xxds
0 (d2--dy) dy)
+ Aldz 17
4
W
2
(=1 [ 1=1
[2
+ dl
Al d dy 17
Applying the definition of X (eq. (34)),
(()
W
L
L B
element-wise.
(37)
i=1
1=1
Therefore, the output of the second layer after the activation
((2) [w:]]
B I.
(2(2)
[w:]] I.
B/ 1.
i=1 )
=
1
1=1
W
[i i=1) )
+ A 1
8
Alds dy 1%
[w:]] 1.
Mcanwhile, the output of the third layer before the activation is (3(
[6 (-1
can be
1=1
calculated based on (2)
[w:]]]
[6 1=1
i=1
5-(3) (1wx)] i=1
[3]] 1
W3r(2)
([x:]]
L
L
=
+
i=1
i=1
[6p] 2
dy
W
+ Alay 17
Eiit
s+
i=1
v=1
X1 2-2- dy 1
[
1
2
Al 17
i=1
i=1
O(da-dy) ) xm
Applying eq. (37),
(0)
(w>))
1.
[6]]
0 clement-wise.
(38)
1=1
:=1
Therefore, the output of the third layer after the activation is
(3) (w>]) 1-1
[=)
[8] L
h (7:0)) (( [
[
89
i=1
i==
([wx] i=1
((3)
-8
(
([w, <[v]]
12
[1 i=1
+ Aldy 12
i=
8
(dg-dy)xx
27

---

Published as a conference paper at ICLR 2020
Suppose eqs. (35) and (36) hold for 1o (3 - k S L 2), when & + 1,
(((++)) W 1.
(=) = W ((k)
[6 1.
[[>:] i=1
[8]
+ b/+1 1
i=1
dy
y
W.
i=1 [b i=1
+ Aldy 17
1
Fri
84
84
(d2 )y)
Ti 2
W
+ AI 1
/=1
i=1
0 (du++ )x
Applying eq. (38),
L
[8]] i-11 [m). 2 0, element-wise.
((++1)
(39)
Therefore, the output of the (k + 1)-th layer after the activation is y((+1)
[w]] L
[6]
(p(att)
[w/
L
-h..... .++
i=1
1=1
i=1
1=1
(((+2) -
([ixz] 1.
[b]]
i=1
i=1
y
W ?
[0m]2]
[B,]
+ Al 17
i=1
i=1
Oc22+ dy)
Therefore, eqs. (35) and (36) hold for any i E (3, 4, ..., L 1).
Finally, the output of the network is
4 L [B1] [b)]_] =x(1)
((w:)
i=1
i=1
(())((11)
([77)
L
[3 i=1
+ B1,17
i=1
(113)
2
[b.]] [b.]2.)) + Al 17
1 dy
Ei,
s_
im
84 1=1
Aldy 1.T
[1i]]] 12
[6.]] 2
i=1 )
i=1
Applying Theorem 4, we have
R
[ [w]]_..
am1 [
[w]]
L
R
2
<(W).
i-1
The proof is completed.
A.4 STAGE (3)
Finally, we prove Theorem 1.
This stage also follows the two-step strategy.
Step (a). Construct local minima of the loss surface.
28

---

Published as a conference paper at ICLR 2020
Lemma 6. Suppose is non-differentiable point for the piece-wise linear activation function h and a is a constant such that the activation h is differentiable in the intervals (t - G, t) and (t, t σ). Assume that M is sufficiently large positive real such that
1/1
1 M
|
8,11% <.
(40)
Let Or be any positive real such that
a1
0 < a.
< 1, i i= 2,
(41)
Then, under Assumption 3, any neural network with piecewise linear activations and L 1 hidden layers has local minima at
W
Wi, 8
By tldi
M
M
11 B/s (i= 2,3, 3,., 1),
W = a.W, By - - W/h((()) + tld, +
M
and
M
W = T 2
MW,, 8%
Wih(t)ld,., +B/
where [w]]] [wo]] i=11 [4. ] is the local minimizer constructed in Lemma 5. Also, the loss is
tinuously differentiable, whose derivative with respect to the prediction Y, may equal to only when the prediction Y4 and label Y, are the same.
lim 1i(0). Proof. Define s lim (0) and 84 P--U+ e-0
We then prove by induction that for all é [1 : L 1]. all components of the i-th layer output before the activation (
(Iw=r) i=1 [0r]
[0=][_]] are in interval (t, é σ), and
y()) [w=]] (-1 [88]
4 L ) m(1)1a, 17
= IT aj (()
([w:] i-1 [81] [b]] [
M
The first layer output before the activation is,
L :-1 [xx]_ [_) W 1 ( (w.T))
wix + 1 1 + U1, 12
(42)
M
M
We proved in Lemma 5 that WiX + 8/ 12 is positive (element-wise), Since the Frobenius norm of a matrix is no smaller than any component" ' absolute value, applying eq. (40), we have that for all i [1, d1] and e [1: n).
(w/x (811%) is
<a.
(43)
M
Therefore,
+/2 (wix 11
+t
E (t,t+ to). So.
ij
y(1) ([1:r] 1
13 1=1)
=h (ww))
[w:"] L
i=1 [88] 5=1 (())))
i=1
how.et
1
wix
1 1 1111""
+h(t)la, 1
M
M
1 y(1)
([w:]] 1=1 [8]] i=1
+ +h(t)1d, 1
M
where eq.(*) is because for any x E (1 0, +)),
h(x) h((()
hy
h
, (xr 1).
(44)
29

---

Published as a conference paper at ICLR 2020
Suppose the above argument holds for (1 S k
L 2). Then
y(++1)
[6:]
i=1
-W r(k)
([1x=) L
b." i=1
+ 8% 1
i=1
-(-0x4 (412((())ddn)
I as 1 + ax+1 W ([Mv:]]
[8g]
tidea1 +
M
i=1
-0k- Wh+t (n(()1, 17 + 11 - [WV]]]
([w:]]
L
[64 i=1
M
i=1
11 aii
+
aa h())((( + +Ildx11 +
171
M
++ 1-1 ai
W k+1
((k)
[w:]] i=1
[6]] i-1 [b]]_.]) +
11k-11
Oci
Bb+t
1 +
(1 17
M
M
-1d,, 1s
II k+1
i=1
(k+11)
[[w:]] / [06]] [183]]_>1881 [
1
M
Lemma 5 has proved that all components of y((k+1) (1+r1) 1
[6]] ) are contained in
i=1
y (Im:]" |- [6]] )
Combining
([re:] & 1-1 [8]]_)))))) < (t <t+
tla, 1h tla 1 + f-2))
M
we have
II k++ os ((+11)
L i- [8]] ([ (.)). 1 (1+o))an
Ud 1 < (1 1
+
M
Here are all element-wise and inequality (+) comes from the property of (eq. (41)).
Furthermore, the (A: + 1)-th layer output after the activation is
y(++)) (Iwr)) L im1 [or] [80]21) =h (p(t-1) ([Trr] L
[g]] L
i=1"
imm
1 g(et2)
[
[8:] i=1
=h (1 (1dr 1 +
M
i=1
hh(t)1d 1 + haawes
11++1
1=1
((++1)
([w::]² ;=1
[8 t.
M
I az M
(((+1)) (wxx] 7
[8 (1))
=h(t)]dr- 1s
he hamrs
i=1
I (l++1)
t. [[wr]*
(=1 [ To )
-h(()) 1 1
M
where eq. (+) is because of eq. (44). The above argument is proved for any index k E (I....,I.-1)
30

---

Published as a conference paper at ICLR 2020
Therefore, the output of the network is
y())
[
i=1 [8"] L
1=1)
W
[[n:]] i=1 [6m]
1
+ 67
M
II ai (1--))
[1::]= i=1
[6 L
WL
h(() 12
M
ai
M
W2b(1)1de de-1 + +//1 1T
+
11
a;
[[x::]=n
/ imm [8]] [B]]__.) 6/.1%
([:t:]=1 i=1" [b/]=]
L
=y(4)
Therefore,
R (wwr)) i=1
[8g] [
R ([ir]]
1 ( [6]] [b]] s(W).
i
{ (1o -
18%1 } into { [
1.
[86) 1
We then introduce some small disturbances order to check the local optimality.
2-1 in
Since all comonents of (1) are in interval (t, (o), the activations in every hidden layers is realized at linear parts. Therefore, the output of network is
4 ([iv'' sw: i=1
+ 8%
i=1
(WE + OWLL
(....tt((W"'++ +ww1) X (6%' + 8% 17).... ) + (0% + 8%L 1
(W% + o%v1
8+ (1.-s+ ((W7 + 8ivn) x + (6% + %% 1 ) + f(t)1d, 1 ...).
+ I())aa, 1"
+
(0% + 8% 1
-MiX + M2
X
= [M
M2]
1
Similar to Lemma 5, [Mi
M2] approaches W. as disturbances {loril 1dull 1 approach 0
(element-wise). Combining that W is local minimizer of f(W), we have
R
i + oir
8 + 5% ) {[M1 Mz)) 2 S(W)- = R 1=1 [Br] L
[+(]_]
The proof is completed.
Step (b). Prove the constructed local minima are spurious.
Proof of Theorem I. Without loss of generality, assume that all activations are the same.
Let t be a non-differentiable point of the piece-wise linear activation function with
lim N (())))
lim h h())).
84
0-401
31

---

Published as a conference paper at ICLR 2020
Let be constant such that h is linear in interval (t and interval (t, O).
Then construct that
1
W" = M
Wi. Dy
M 11 (ldi
1
1
W =
W2, 8y = d1 - htt htt + 8/2
M
M
MM
W." W. 8 - + tld, + 8/, (i = 3.,, 1)
MM
and
= MMWL 8L = 82 MMM11(()1L-)
Ww L
where
are constructed in Theorem 5, M is large enough positive real such
that
1
+ [11x+11111 <a,
(45)
M
and M a large enough positive real such that
1 ((2)
(IH1)
L 1-1
[1 ( <a.
(46)
M
M
Then, we prove by induction that for any i E 12 L - 1]. all components of 1.
[ [_) are in interval (t, t + 8), and
40 i-1
L L (()) (Iw:]]
im1 [0:]__) - h(1)1a, 1
L i-1 [34] [B)]_) ([wr]
y(i)
MM
First,
(())
[
[6:] (mm)
L [
W 8.
1 M
( + +8,13) + +115
(47)
For any E [1 : di] and j E [1 nl. eq. (45) implies
( +
S SM M
Wix + +811% <o.
Thus,
+ (11 + (11x+01h++41111
E(t-o,t+o).
(48)
Therefore, the output of the first layer after the activation is
y(1) [W!"] & i= [ (
[3g] 1
L ([177)]
19 i=1
i=1
1
(WiX + 11111) + tid, 12
M
h(t) 1st + h (1) (wixx + Bi))
M
=b(t)La, 1s Ma ((wix + Bi))
M
[w<:]] L L
h(t) 1
y(1)
M
32

---

Published as a conference paper at ICLR 2020
where eq. (+) is from eq. (44) for any (t - -6,++))
Also,
(2)))
[
b5'
=W
([x::) i=1
8"" (=1)
[=1
1=1)
+
1
(w:)
(n(t)I,, 1
1 y(1)
[[1:]] L
1=))
M
M
i=1
+ M1 +1,11
- h())
1
1211
M
MM
wyy (1)
[M>:]]
L
16 i==
b, + f1 1,
MM
i=1
MM
(-12)
(w<)]
[6]]
11d,17
MM
1=1
1=1
Recall in Theorem 5 we prove all components of (2(2) ing the definition of M (eq. (46)), we have
(w7x) 1
B8] ())).)) are positive. Combin-
i-1
[ -==1"
L
f1 1T n <8
7(2) ([w:]]
5.
[6 1. ) + 17
MM
1=1
< (t + o o)ldd
Therefore,
y(2)
[1:7]] i=1
[py] i=1
=h (1(2) ([w::)]
[34] i=1
i==
=h
y(2)
[WN]] i=mi [b]] [b]]][]
+ flld 17
MM
11 -(2)
=h(()1a, 1T + ha
MM
i=
=h(t)La,17, 17 + MM ha-184
(x(2)
(Iwr)
1 (()
[w]] L
[(t]
-h(1)1a,77 1
MM
i=i
i-11)
Suppose the above argument holds for k-th layer.
The output of (k 1) layer before the activation is
(x+1)
[w::][]
6
i=1
-W (())
(1x:00]] 1
i=1 [B:]
86+ 1T
-We+1 ((t))a + MM
1 (())
[w::] [-
[B] i=1
(- Wh+rh(t) tlldn
1s.
MM k
1
(WLL) (a) ([w:]] -=
[B] (
+ bb
+ +1 +tdr 1s
MM
1
((++1)
[i.:]]_]
L
[B]]
L ( 11
1l 1
MM
33

---

Published as a conference paper at ICLR 2020
(wx)] i=1 [1]] :=1
[ except those that
Recall proved Theorem 5 that all components of (k+11)
[ i=1 [64 L
are 0 are contained in (k)
We have
1 p(k-1)
1. ([v::]"
[6 (0))
f1 11
[=
+ldd 1h < (t+ (t
MM
Therefore,
y((+1)
[ i=1
B3]] i=1
h (()))
L
[85] L
i=1 1
h 1 g(++2)
[W: [ [6]] 1-1 [ +1dz+ 1
MM
1 y(++1) ([m:3] i-1 [8]] [3]=-))
de 1.
MM
Thus, the argument holds for any & (2, .2,..., 1}.
So,
y(v) (11:00] i=1 [b.]]] (-1 = =Wy((L-1)
([#:"] i=1 i=1 + 3%
[
-MMi. h(t))dd., 1 y(L-1) ([.=:1__.<<11_))))) ())
[B]]
AM
11 -MMMWM .17
-x(()) ([w?]] {
Therefore,
L R (w::) ji=1
(5y) (im)) R (117)) i=1
86 )
(49)
From eq. (49) and Theorem 5, we have
1. R
[
< (w))
i=1
i=1
which completes the proof of local minimizer.
Furthermore, the parameter M used in Lemma 6 (not those in this proof) is arbitrary in continuous interval (cf. eq. (40)), we have actually constructed infinite spurious local minima.
Theorem relies on Assumption 4. We can further remove it by replacing Assumption 3 by mildly more restrictive variant Assumption S.
Corollary 3. Suppose that Assumptions 1, 2, and 5 hold. Neural networks with arbitrary depth and arbitrary piecewise linear activations (excluding linear functions) have infinitely many spurious local minima under arbitrary continuously differentiable loss whose derivative can equal 0 only when the prediction and label are the same.
Proof. The proof is delivered by modifications Theorem 4 in Stage of Theorem proof. We
only need to prove the corollary under the assumption that 8 + 84 0.
Let the local minimizer constructed Lemma 4 be
[w]] 1=1
[
Then, we construct a
point in the parameter space whose empirical risk is smaller follows:
34

---

Published as a conference paper at ICLR 2020
Wi.d o.
Wi.[lsxx]
-Wi,jtixll + OB8T W2[11dx]
W1
[lxx(
(di -2)xxxx
W Wi]dx+1]] - ?/1 Y
Wl, 17
-W1,1dx+1] +111 +
b
W2,dx+11 1/2
Way [dx+1] +1| ndy
(d, -oiydd-- dy -2
2+
28
0
0
0
1
0
W/2
0
0
0
0
0
0
and
r
1/2
b2
Tdy
where a, B, and T7, are defined the same as those in Theorem and n defined by eq. (27).
Then, the output of the first layer is
Y(O) ([w,]² 1= [b 1=1 -he
[b]]=]]
(WiX + b,1
Wi.X -.8Tx X 171 1T + 71
Wr.X 111
- X a X m 17 + y1T
-h4
W₂. X 12
dy X n T
02 -d -2
T
35

---

Published as a conference paper at ICLR 2020
Further, the output of the whole network is
y
WW i=1 i-1 )
b,
Wi,X - a.3T X 1/1 17 + t 7
W1, - -111%%
-W1, X + a.3 X + 11 +
=Wahs
W X 1
b2
T
72
W Wyy X
nd T
Odg-dy 21
W X 0.3 X 1/1 1 + 7
W1,.X X - 1/1
W,, X + aB X 1 + 7
T/2
= WWhha_i
W2, W 12
1 13
W dy X Bdy 1
Od -dy 21
Therefore, if S I., the (1,j)-th component of y
[w:]
1
3
i=1
im1
W 2
(W2)
f(1)
i=1 ==1
(F2. as x, - + +7) + 22+ (Fi. 1) - (-h1, + m +7))
s-_
2s+
+1
1
(-s+ (F2,) - a.8 mn +,) + 2s+ (Fi.s -n) s+ (- + +7))
2s+
+1
1
128 V1.5 - -1847)-28877 2847)
-3447) + 17
28+
=Vi.j
-
Otherwise (j > P'), the (1, component of y ([wx]
[g 1 )
is
i=1 1-1
(Wb) 1
f.1) [w:]² i=1
[6 2 1=1
(fi. a33" xj +7)
+ 22+ (Pis -n) -- (-81s +83 +
28+
+ 7
1
(8+ (Y1,3 aT3 x 1h +7) + 2s+ (Yr. -n) s+ (-Y1, a.3 x, - +7)) +
284
1
(2s4V1, Vi,5 28 + 2847) +
-2s
=Y1,
+7,
and the (t, (i > 1) component of & ([w:)²
1
1x2 i=1
is Vag
i=1
36

---

Published as a conference paper at ICLR 2020
Therefore, we have
7.
j j=1,is
W2 [122 + b1) + bz vi [
7:
4 j22 2.
0,
Then, similar to Theorem 4, we have
[b.] [=1 - R ([wi] [
[ i=1
R
W.
i=1
i=1
1
(Y,, We (Wiss: + b1) + b2)
1
Yi; W 22
11
n1
Yi v [24] We (wiz; + 8n 1m)
+ b2 - w [2)
Vy.
[1]
zj (1 W/ [wix; + b111)) + 521 w
1)
+
Σ
1
1=1
2
V1.7+
where V and are also defined the same as those Theorem 4.
When y is sufficiently small and sgn(7) = sgn
EE Vi.s). we have that
((1 W
b )=1 ))
R
< x(W)).
i=1
This complete the proof of Corollary 3.
A.5 A PREPARATION LEMMA
We now prove the preparation lemma used above.
Lemma 7, Suppose = (u1 ..,)) E IRlx which satisfies u o 0 and
Σ =0 0,
(50)
while {x set of vector Rx Suppose index set S = (1,2.... ,n.. Then for any there exists non-empty separation I, J of which satisfies IUJ J= == and both I and J are not empty, a vector 3 Tg ,such that,
series of real number (V1, ..., Vn
flr1) any sufficiently small positive real a, i E I, and j E J, we have 14 a z4 < 0: Zz; (1.2) Eier us # 0.
Proof. If there exists a non-empty separation and J of the index set S, such that when , = 0, (1.1) and (1.2) hold, the lemma apparently correct.
Otherwise, suppose that there no non-empty separation I and of the index set S such that (1.1) and (1.2) hold simultaneously when 0.
Some number v; in the sequence (vi, U2, ,,)) are probably equal to each other. We rerarrange the sequence by the increasing order follows,
02 Ua, < Uni+1 Usz
Uaa- 1+1
Uog
Uns
(51)
where 8): n.
37

---

Published as a conference paper at ICLR 2020
Then, for any E (1,2, -- - 1}. argue that
Σ
0.
1=1
Otherwise, suppose there exists 8y, such that
8j
Σ
Let / (1,,, 83} and J {8) + 1,... n). Then, when 0, have
0 - a.5 84
V/ = Dj a.3 Zj
Us
and
Σn
Σ 14
0,
SET
1=1
which are exactly the arguments (1.1) and (1.2). Thereby we construct contrary example. There- fore, for any j E (1,2, 2. ,h- 1}, we have
Since assume that e O, there exists an index E (1,...,k k- 13, such that there exists an index i {st + L,..., Sc+1} that u, * O.
Let I E {st + 1,..., 8141 is the index such that z; has the largest norm while u; + 0:
arg max
||>
(52)
We further rearrange the sequence (Us.+1, u.y Uorrs such that there is an index 1' E {st + 8141).
| || I uy0 |05ll
max
and
Vie (8t + I,... I'), (Fr, 2 || 11= Wi Wi (1' + +,, 88-1), (m)) < ||
(53)
(54)
worth noting that it is probably 1' 8141s but it is a trivial case that would not influence the result of this lemma.
Let (L...., 1'), J = 11' I,....n) n). and 3 = xr. We prove (1.1) and (1.2) as follows.
Proof of argument (1.1).
We argue that for any E I, v/ a; xs S up az3 ay and for any j E J, Uj - 018 xx >
Up - a xy.
There are three situations:
(A) (L.....s) 9t} and j E {st+1 + 1, ,n). Applying eq. (51), for any i (1...., 3/} and j E [st+1 1.... n). we have that v, < uy and oj > up. Therefore, when is sufficiently small, we have the following inequalities.
2: a xi Av a. xv.
- TT x3 > vy - az33T xv.
(B) E {sc + 1, ,1}. Applying eq. (53) and because of a O, we have
(a(3,I;) || -a zv))
38

---

Published as a conference paper at ICLR 2020
Since 02 up, it further leads to
a 2i S vp aB" xV.
(C) E (1' + 1, 8.+1). Similarly, applying eq. (54) and because of >> 0, we have
2g) > a ||311 = - a(8,2r))
Since Uj = uy, further leads to
0/ - 2ÿ vy a. xv,
which is exactly the argument (1.1).
Proof of argument (1.2).
We argue that for any i {st + 1,.... 1' 1}. O. Otherwise, suppose there exists E {ot + +1, -,,,,,, }} such that u, + From eq. (52), we have || S | Therefore,
(rv.z)) S | ||||=|1| S ||
where the first inequality strictly holds if the vector zy and x; have the same direction, while the second inequlity strictly holds when v; and xv have the same norm. Because zy + xg we have the following inequality,
(.)) < ||
which contradicts to eq. (53), i.e.,
(mr, x.) 2 || 113, Vi E {st + ,.)
Therefore,
Σn,
U4
U4 + uv = up + 0,
EE
1=1
(=
which is exactly the argument (1.2).
The proof is completed.
Remark. For any E {L' I,..., St.1) J. we have
(4- a.3 x1) (wr aB 21)) ax -x)).
(55)
while for any j {sL+1 + I,..,, n), we have
(vz - -33 a;)) (ur - a1 xr) = = - Ur + 3r (xx - xz))
(56)
Because vi > up, when the real number or is sufficiently small, we have
aB (xv .44) < Dj br + or (ay - x.2).
Applying eqs. (55) and (56), we have
(v: aT x.)
(wy - a,8 2v) < <11 - -a.3 (vr aBFarr)
Therefore, ifl' 8t+1, have
min :E((+I.....))
(vs a.3 - (1) - a.3 xv) = min a.5 (xr - xz))
(57)
while ifl' = St+1
(v: TT) (vr cr min Vi U1 + a,3 3Tv xz). (58)
ie(U sE(U-1....))
sE(F+1.....
Eqs. (57) and (58) make senses because < n. Otherwise, from Lemma 7 we have E Ui + 0, which contradicts the assumption.
39

---

Published as a conference paper at ICLR 2020
B PROOFS OF THEOREM 2, THEOREM 3, COROLLARY 1, AND COROLLARY 2
This appendix gives the proofs of Theorem 2, Theorem 3, Corollary 1, and Corollary 2 omitted from Section 4.
B.1 SQUARED LOS$
We first check that the squared loss is strictly convex, which is even restrictive than "convex". Lemma 8.
The empirical risk R under squared loss (defined by eq- (5)) is strictly convex with respect the prediction Y.
Proof. The second derivative the empirical risk R under squared loss with respect the predic- tion y is
Plee
Ply-Y²
2>>0 0.
042
0
Therefore, the empirical risk R under squared loss is strictly convex with respect prediction Y.
B.2 SMOOTH AND MULTILINEAR PARTITION.
If the activations are all linear functions, the neural networks is reduced to multilinear model. The loss surface is apparently smooth and multilinear. The nonlinearity in the activations largely reshape the landscape of the loss surface. Specifically, if the input data flows through the linear parts of every activation functions, the output falls in smooth and multilinear region in the loss surface. When some parameter changes by sufficiently small swift, the data flow may not move out of the linear parts of the activations. This fact guarantees that each smooth and multilinear regions expands to an open cell. Meanwhile, every nonlinear point in the activations non-differentiable. If the input data flows through these nonlinear points, the corresponding empirical risk is not smooth with respect to the parameters. Therefore, the nonlinear points activations correspond to the non-differentiable boundaries between cells on the loss surface.
B.3 EVERY LOCAL MINIMUM IS GLOBALLY MINIMAL WITHIN A CELL.
Proof of Theurem 2. In every cell, the input sample points flows through the same linear parts activations matter what values the parameters are.
(I) We first proves that the empirical risk R equals to convex function with respect variable W that is calculated from the parameters W.
Suppose (W1, 1, W2) is local minimum within a cell. We argue that
Σ (vs. W2diag (A.,) Wix;)
(59)
where A. is the i-th column of the following matrix
Wr . (W11),,211
M1 ot ((W1)),
A
(60)
1/ .s1 (WW))
h. i ((Wi)
The left-hand side (LHS) is as follows,
LHS (vt, Wydiag (A.,) Wix))
(v., ((W2),,,11
(W2)1,, W1x:).
40

---

Published as a conference paper at ICLR 2020
Mcanwhile, the right-hand hand side (RHS) is as follows,
RHS Σ (y), diag(WW)))1z.))
Σ (yi. (WW2),,11
(aaaa,,A,, WIx.).
Apparently, LHS RHS. Thereby, proved eq. (59).
Afterwards, we define
W1 = ( W1,
(61)
and then straighten the matrix W, to a vector W,
W ((W)2,
(Wi)dr))
(62)
Also define
X = (A., & 21 Then, prove that the following equations,
A. @ xn).
(63)
(A7,Wa1
A,, AT, (1,) = ((W)), (Wi)dr.) (A,1 @ x
A & 2n.)
=WX.
(64)
Applying eq. (64), the empirical risk transferred to a convex function as follows,
1 n
R(W,, W2)
Uis (A) diag (W2)
Σ
(A. Wiz;)
yor (A.,))
12
Σ
(v, W Wx).)
(65)
We can see that the empirical risk is rearranged convex function in terms of W which unite the two weight matrices Wi and W2 and the activation h together as W. Applying eqs. (61) and (62), we have
W (W1),, ... (W2)a, (Wi)
(2) We then prove that the local minima (including global minima) of the empirical risk π. with respect to the parameter W also local minima with respect to the corresponding variable W. We first prove that for any E [1 di dzd,), we have
c. = 0,
where V is defined as follows,
V \ (wx)) / (M, (mx),
V(Wxx) (Fr (wx) )
To see this, we divide into two cases: (W2); # O and (W2), = O. Case 1: (W2); 0.
The local minimizer of the empirical risk π with respect the parameter W satisfies the following equation,
oR 0.
a(W1) k
41

---

Published as a conference paper at ICLR 2020
Therefore,
0
a(W))s
Y, (WX) (Wxx),,)
:k )
0 Σ
a(Wi)es
Σ
(W2);
0 1 (Wx8)
(( I (v.5s,
(wx))..)
(66)
dxd, (x-1)-((-1
where (W2) is vector and (W2); is its i-th component. Then, divid the both hand sides of eq. (66) with (W2)i, we can get the following equation,
(cdx(1-1+) 0.
Case 2: (W2); = O. Suppose u1 E Rd a unitary vector, U2 E R a real number, and æ is a small enough positive constant. Then, define disturbance of W1 and W2 follows,
AW1 = 0
EU1
0 1,
(x
dxxx-xx
AW2 =
E²
0
].
When is sufficiently small, AW; and AW2 are also sufficiently small. Since (W1, W2) is local minimum, we have
1
Yks ((W= ))
+
n
RR( + AW1, W2 + AW2)
RR(W,, W2)
Ykk, (wx)))
(67)
where defined as follows,
A [[W2 + (W1 + AW1)
(W2 + AW2),, (W1 + AW1)a.
(W1)) (W2)a, (W1)..)
0
Eu (au + (W1).)
0
(68)
dx(t-1)
dıdx - dxi
Here, eq. (x) comes from (W2), = Rearrange eq. (67) and apply the Taylor's Theorem, we can get that
A X - x11² 20 o.
42

---

Published as a conference paper at ICLR 2020
Applying eq. (68), we have
0
EZ (Eu) + (Wi)s) 0 0 o ]xv
dx(i-1)
dxdi -idx
+
(111 0
0
U2 (Ea1 + (W1);
0 1x11²)
dx(i-1)
dxx
(+0)
E
uuuu 0
XV
dx(t-1)
Axd1-ids idx
+
U2 (Eu1 + (W1)+)
0 1x(11))
dx(1-1)
dx -dx
33 0
Uz
0 OIXV + o
(69)
(x(1-1 dxd idx
20 0
(70)
Here, eq. (**) can be obtained from follows. Because W2 is local minimizer, for any component (W2); of 22
Ek= (Ya, (wx))
=0,
O(W2)s
which leads
(Wi);
1&V= = 0.
(x-1-1)
dy idx
When approaches 0, eq. (69) leads to the following inequality,
[ 0
O
U2 U
2XV 2 0.
(x-1-
dx
-idx
Since u and u2 arbitrarily picked (while the norms equal 1), the inequality above further leads to
[
O 0 0 = 0,
(71)
dx
dix
which finishes the proof of the argument.
Therefore, for any and j, we have proven that
(doli-1)t XV=
which demonstrates that
XV = 0
which means W is also a local minimizer of the empirical risk R.
R(W) = Σ (Y, WX))
(72)
(3) Applying the property of convex function, W is global minimizer of the empirical risk R, which leads to (Wi, W2) is global minimum inside this cell.
The proof is completed.
43

---

Published as a conference paper at ICLR 2020
B.4 EQUIVALENCE CLASSES OF LOCAL MINIMUM VALLEYS IN CELLS.
Proof of Theorem 3 and Corvllary In the proof of Theorem 2, we constructed a map Q: (W,, W2) + W. Further, in any fixed cell, the represented hypothesis of neural network is uniquely determined by W.
We first prove that local minima in a cell are concentrated as local minimum valley.
Since the loss function I is strictly convex, the empirical risk has one unique local minimum (which is also global minimum) with respect to W in every cell, if there exists some local minimum in the cell. Meanwhile, we have proved that all local minima with respect to (W1, W2) are also local minima with respect to the corresponding W. Therefore, all local minima with respect to (W1, W2) correspond one unique W. Within cell, when Wi expands by a positive real factor to Wi and W2 shrinks by the same positive real factor a to W we have QW,, W2) = Q(Wi, W2), i.e., the W remains invariant.
Further, argue that all local minima in cell are connected with each other by continuous path, on which the empirical risk is invariant. For every local minima pair (W,, W2) and (W,, W3), we have
diag(W))W, diag( (iag(W
(73)
Since Me (W1X) ,2, (W(X) (element-wise), for every i [1,d]].
sgn ((W2),) sgn ((W2),)
Therefore, continuous path from (W1, W2) to (WI, W2) can be constructed by finite moves, each of which expands a component of W2 by real constant a and then shrinks the corresponding line of Wi by the same constant
We then prove that all local minima cell constitute an equivalence class.
Define operation ~R follows,
(W). w:) ~R (W?, W2),
if
Q(W) w3) = Q(W? ((W??W3) W3)
We then argue that <aR is an equivalence relation. The three properties of equivalence relations are checked as follows.
(1) Reflexivity:
For any (W1, W2), we have
Q(Wi, W2) Q(W,, W2).
Therefore,
(W1, Wo) ~R (W1, W2).
(2) Symmetry:
For any pair (W7, W:) and (W?, W3).. Suppose that
(W),W;) ~n (W?, W2).
Thus,
Q(W. w/)) Q(W?, W3).
Apparently,
Q(W?, wW) Q(W] W!).
Therefore,
Q(W?, W2) ~R Q(W..W3)
(3) Transitivity:
44

---

Published as a conference paper at ICLR 2020
For any (W1, W2), (W?, W2), and (W?, W2), suppose that (W). W2) ~AR (W?, W2), (W?. W2) ~R (W?, W.).
Then,
Q(W),W)) = Q(W?, W Q(W? w2) - =Q(1, W3).
Apparently,
Q(I W3) Q(W?, W2) Q(W?. w3).
Therefore,
(W1. w:)) ~R (W W3)
We then prove the mapping Q the quotient map.
Define map follows,
T: (W1, W22 + (diag(W2) 11xd1).
We then define an operator + as,
(W: W:)) (W7. W3) - (WW W:') T W2).
the inverse of (W1, 22) is defined to be (-W, W2) and the zero element is to be (0. 1ixd;) )-
Obviously, the following is a linear mapping:
Q: ((I xdx IR 1xdxd)), ), +) + (R 1xdxxx +).
For any pair (W7, W2) and (W?, W2), we have
(W1, W.)) ~R (W?, W
and only if Therefore, the quotient space (R xdx R 1xd1) Ker(() Q) is definition of the equivalence relation
(W1) W:2) + (-W?, W2) E Ker(Q).
~n-
The proof is completed.
B.5 LINEAR COLLAPSE.
When there no nonlincarities in the activations, there is apparently no non-differentiable regions on the loss surface. In other words, the loss surface is single smooth and multilinear cell.
45


Reviews:
[{"review_id": "SJxEpgtGcS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Summary: This paper studies the landscape of deep neural networks with piecewise-linear activation functions. The paper showed that under very mild assumptions, the loss surface admits infinite spurious local minima. Further, it is shown that the loss surface is partitioned into many multilinear cells. If the network is two-layer with two-piece linear activations, it is proved that within each cell every local minimum is global. \n\nPros:\n  --Constructed spurious local minima for piecewise linear activations, for a broader setting than previous papers. \n  --The paper is well written, with detailed explanation of proof skeleton. \n\nCons: \nThe significance of the results are not clear. Details are given below. \n\n1.\tThis paper only considers piecewise linear activation, which is a special type of non-linear activation. The major examples are ReLU and leaky ReLU. However, related results for ReLU have been studied for a few previous works mentioned in the last two paragraphs of Sec. 3.2. In particular, Yun et al. 2019b already proves a similar result for 1-hidden-layer neural-net with ReLU activation. I think extending the construction to broader settings (any depth, any piecewise linear and more losses) is mathematically nice, but the motivation of this extension is somewhat unclear to me. One motivation is that this is helpful for the purpose of understanding a “big picture” of the landscape, which I will discuss next.\n\n2.\tThe second major result is Theorem 2, on the “big picture” with ReLU-like activations. However, Theorem 2 is somewhat trivial to prove, and the link to Theorem 1 is rather weak.\n   (a) The main message of Thm 2 is the partition of the surface into multiple pieces, and each piece has good property. This partition is somewhat straightforward, and has been studied before, in, e.g., [R1].\n   For a global “big picture”, partitioning itself is not very interesting. Theorem 2 mainly describes the property of each region separately for 2-layer network, which is weaker than [R1]. \n   (b) Theorem 2 seems easy to prove. The 1st, 3rd and 4th property are all straightforward. The 2nd property “local analogous convexity” was given a 2-page proof in the paper. However, I don’t understand why not use the following simple argument: for each region, the network behaves like a deep linear network, thus directly applying existing result shall imply “every local minimum in the region is the global minimum of the region”, right? If not, what is the difficulty?\n   (c) The 3rd property says “some local minima are concentrated as a valley in some cell”. What are the formal definitions of “concentrated” and “valley” in this sentence?\n   (d) The link to Theorem 1 is weak: the link is the 3rd property of Theorem 2 that “some local minima are in a valley”. It is just about some special local minima and weakly related to the other properties on the “global view”. In addition, the fact that “some of them are in a valley” may be due to the very special construction, thus it is not surprising and does not reveal anything interesting about the “big picture”. \n\n\n3.\tOther issues:\na) While ReLU-type activations are popular, there are still commonly-used activation functions are not piece-wise linear, e.g., tanh, swish. It is not proper to claim that \"this paper presents how nonlinearities in activations substantially shape the loss surface\" and \"almost every practical neural network ....\". I suggest replacing \"nonlinearity\" with \"piecewise linearity\" in both the title and the abstract, and modifying the over-statements. \n   b) In Property 1 of Theorem 2, “smooth and multilinear partition” might be a bit misleading. The loss surface should be fractional in general, where multilinear cells are separated by non-smooth boundaries. “Smooth partition” seems to imply that the boundaries are smooth or the partition method is smooth in some sense.\n   c) The name “analogous convexity” is not appropriate. Analogous convexity is not formally defined in the paper. According to Sec. 4.3 third paragraph, “the property of analogous convexity that the local minima wherein are equally good”. It seems that “analogous convexity” is just “all local minima are good”, which is very different from convexity. It is a weaker property than quasi-convexity, star-convexity, etc, and thus it is better not to call it “analogous convexity”.\n    d) Property 3 of Theorem 2 is very far from “mode connectivity”. The proof of Property 3 relies on a special construction of Theorem 1, and the latter is for two arbitrary global minima. \n\n\n[R1] Soudry and Hoffer. \"Exponentially vanishing sub-optimal local minima in multilayer neural networks.\" arXiv preprint arXiv:1702.05777 (2017).\n\n\nConclusion:  I think this paper is studying an important and interesting question, and the efforts of constructing local minima and understanding big picture are both interesting to me. However, I’m afraid the current form of the paper does not meet the standard of the conference. That being said, it would be a nice paper if the big picture can be explored deeper, and the link to the spurious local minima can be built stronger. \n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "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": "Bkl1dQB2YH", "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 focus on how activation functions’ nonlinearities shape the loss surface of neural networks. The authors first show why the loss surface of every neural network has infinite spurious local minima. Secondly, the authors prove one theorem to show four properties of the loss surfaces of nonlinear neural networks.\nAlthough this paper is generally easy to follow, and the motivation about nonlinearities and the loss surface is clear, the insight of this paper is somehow shortcoming. Though this work can prove such properties within different preconditions, whether other works’ conditions are inconvenient or not may remain further discussions. This work is established based on several preconditions, while it is hard to assert that most kinds of neural networks can satisfy them perfectly. For instance, this work mentions “Deep learning without poor local minima (NeurIPS2016)”, which requires full-rank and conditional independence of each node. It could be feasible when training a stacked network with particular limitations. This work requires all hidden layers are wider than the output layer, which may not be suitable for image segmentation, generative tasks or super-resolution, etc. Besides, it is laudable to prove fundamental rules in neural networks, while showing or inspiring researchers about how to implement or approximate such results to improve neural networks might be more helpful.\nSome questions:\n\n1. The authors assert that “the loss surface of *every* neural network has infinite spurious local minima” in the abstract, while in chapter 3 line 2, authors mention, “We find that *almost all* practical neural networks have infinitely many spurious local minima.” Which one is correct? Based on the following description in this paper, I guess this result is conditionally tenable.\n\n2. In lemma 3, authors construct the local minima by adding very negative biases and show they are spurious. However, it is less likely to learn such negative biases in the real case. Besides, some networks require biases equal to zero to achieve some specific target. My question is: if biases are conditioned on real-world data distribution, will lemma 3 and 4 still work in this case?\n\n3. This paper mentions “infinite” many times. Based on the reference, I believe that the “neural network” in this work refers to the “artificial neural network,” which is majorly stored within float tensors. So the number of combinations of parameters is finite. So why use “infinite” instead of “many”? Finite means I can train a small scale of networks with fewer precisions and check the global minima with a fixed dataset.\n\nAll in all, I believe this paper can be significantly improved if more details and experiments are provided.", "extra_scores": {"experience_assessment": "I do not know much about 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": {}}, {"review_id": "B1g3dnrRKH", "reviewer": "AnonReviewer3", "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 theoretical property of neural network's loss surface. The main contribution is to prove that the loss surface of every neural network (with arbitrary depth) with piecewise linear activations has infinite spurious local minima. Moreover, the paper further characterizes the partition of the local minima. More precisely, the loss surface is partitioned into multiple smooth and multilinear open cells and within each cell, the local minima are equally good. This result can also explain the linear neural network case where there is only one cell, implying that all local minima are global. \n\nOn one hand, I find the paper very clear and the result very clean, which unites a lot of existing results. On the other hand, with a reasonable initialization in practice, we will not attain the local minima constructed in the paper since it requires all the activations to be positive. This limits the plausible implication from this theoretical study. Overall, I am very positive of the paper, the following are some detailed comments. \n\na. Please be more precise in the abstract that the activation function need to be piecewise linear. \nThe current sentence \"the loss surface of every neural network has infinite spurious local minima\" does not include this specification. Moreover, if the activation is differentiable, is the claim still hold? It seems to me from the middle of page 3 that Li et al 2018 shows a non-local minima result in this case.\n\nb. How different is the analysis comparing to existing result?\nI have only go through the skeleton of the proof and have not read into the details. It seems to me the construction of the local minima is very similar to [1], since the main idea is to consider the linear region by activating all the neurons. Could you summarize the main difficulty to extend their results to multi-layer cases? (Maybe it would be good to illustrate with a simple case like 3 layers few neurons per layer)\nMoreover, when considering the local convexity, is it sufficient to say that locally in each cell it is a linear network and then the results on linear network transfers to it locally?\n\n[1] Small nonlinearities in activation functions create bad local minima in neural networks, Yun et al, 2019", "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": {}}]

Author rebuttal:

Meta-review: Quoting R3: "This paper studies the theoretical property of neural network's loss surface. The main contribution is to prove that the loss surface of every neural network (with arbitrary depth) with piecewise linear activations has infinite spurious local minima."

There were split reviews, with two reviewers recommending acceptance and one recommending rejection.  During a robust rebuttal and discussion phase, both R2 and R3's appreciation for the work was strengthened.  The authors also provided a robust response to R1, whose main concerns included (i) that the paper's analysis is limited to piecewise linear activation functions, (ii) technical questions about the difficulty of proving theorem 2, which appear to have been answered in the discussion, and (iii) concerns about the strength of the language employed.

On the balance, the reviewers were positively impressed with the relevance of the theoretical study and its contributions.  Genuine shortcomings and misunderstandings were systematically resolved during the rebuttal process.
Decision: Accept (Poster)