PIECEWISE LINEAR ACTIVATIONS SUBSTANTIALLY SHAPE THE LOSS SURFACES OF NEURAL NETWORKS
Year: 2020

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 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 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.

heading: 1 INTRODUCTION
text: Neural networks have been successfully deployed in many real-world applications (LeCun et al., 2015; Witten et al., 2016; Silver et al., 2016; He et al., 2016; Litjens et al., 2017). In spite of this, the theoretical foundations of neural networks are somewhat premature. To the many deficiencies 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.
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 nonlinearities is profound.
First, we prove that the loss surfaces of nonlinear neural networks are substantially different to 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, 2018; Yun et al., 2018). By contrast,
Neural networks with arbitrary depth and arbitrary piecewise linear activations (excluding linear functions) have infinitely many spurious local minima under arbitrary continuously differentiable loss functions.
∗Both authors contributed equally. †Bohan Wang is also affiliated with University of Science and Technology of China. This work was completed when he was a summer intern at UBTECH Sydney AI Centre, School of Computer Science, Faculty of Engineering, the University of Sydney.
This result only relies on four mild assumptions that cover most practical circumstances: (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 piecewise linear activations that the sum of the slops on the two sides does not equal to 0.
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; Swirszcz 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 a 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 extend 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 parameter space whose empirical risk is lower than the constructed local minimum in Step (a). This strategy is 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 a 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 a 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 a degenerate nature of the large amounts of local minima from the following aspects:
• Every local minimum is globally minimal within a 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 rigorously 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 a 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 parameter 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-based 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 a whole.
• Linear collapse. Linear neural networks are covered by our theories as a 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 on linear networks (Kawaguchi, 2016; Baldi & Hornik, 1989; Lu & Kawaguchi, 2017; Freeman & Bruna, 2017; Zhou & Liang, 2018; Laurent & von Brecht, 2018; Yun et al., 2018).
Notations. If M is a matrix, Mi,j denotes the (i, j)-th component of M . If M is a vector, Mi denotes the i-th component of M . Define Eij as a matrix in which the (i, j)-th component is 1 while all other components are 0. Also, denote ei as a vector such that the i-th component is 1 while all others are 0. Additionally, we define 1k ∈ Rk×1 is a vector whose components are all 1, while those of 0n×m ∈ Rn×m (or briefly, 0) are all 0. For the brevity, [i : j] denotes {i, · · · , j}.

heading: 2 RELATED WORK
text: 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 XXT and XY T have full ranks; and (2) the input layer is wider than the output layer; and (3) the eigenvalues of matrix Y X> ( XXT )−1 XY T 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 is 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-parameterized neural networks have some special properties. Choromanska et al. (2015) empirically suggest that: (1) most local minima of over-parameterized 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-parameterized fullyconnected 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 overparameterized” neural networks have no bad local valley under the cross-entropy loss. Nguyen (2019) further suggests that the global minima of sufficiently over-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-parameterized networks (Chizat & Bach; Arora et al., 2018; Brutzkus et al., 2018; Du et 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 are partitioned by multiple regions, while our work focuses on 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 parameterW 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 eliminate the spurious local minima by adding one unit per output unit for almost any neural network in practice. Tian (2017); Andrychowicz 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 et al. (2019a); Kuditipudi et al. (2019); Garipov et al. (2018); Draxler et al. (2018); He et al. (2019); Kawaguchi & Kaelbling (2020).

heading: 3 NEURAL NETWORK HAS INFINITE SPURIOUS LOCAL MINIMA
text: This section investigates the existence of spurious local minima on the loss surfaces of neural networks. 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 activations excluding linear functions under arbitrary continuously differentiable loss.

heading: 3.1 PRELIMINARIES
text: Consider a training sample set {(X1, Y1), (X2, Y2), . . . , (Xn, Yn)} of size n. Suppose the dimensions of feature Xi and label Yi are dX and dY , respectively. By aggregating the training sample set, we obtain the feature matrix X ∈ RdX×n and label matrix Y ∈ RdY ×n. Suppose a neural network has L layers. Denote the weight matrix, bias, and activation in the jth layer respectively by Wj ∈ Rdj×dj−1 , bj ∈ Rdj , and h : Rdj×n → Rdj×n, where dj is the dimension of the output of the j-th layer. Also, for the input matrix X , the output of the j-th layer is denoted as the Y (j) and the output of the j-th layer before the activation is denoted as the Ỹ (j),
Ỹ (j) = WjY (j−1) + bi1 T n , (1) Y (j) = h ( WjY (j−1) + bi1 T n ) . (2)
The output of the network is defined as follows, Ŷ = hL ( WLhL−1 ( WL−1hL−2 ( . . . h1 ( W1X + b11 T n ) . . . ) + bL−11 T n ) + bL1 T n ) . (3) Also, we define Y (0) = X , Y (L) = Ŷ , d0 = dX , and dL = dY . In some situations, we use Ŷ (
[Wi] L i=1 , [bi] L i=1
) to clarify the parameters, as well as Ỹ (j), Y (j), etc.
This section discusses neural networks with piecewise linear activations. A part of the proof uses two-piece linear activations hs−,s+ which are defined as follows,
hs−,s+(x) = I{x≤0}s−x+ I{x>0}s+x, (4)
where |s+| 6= |s−| and I{·} 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 a piecewise linear function to estimate it with arbitrary small distance.
This section uses continuously differentiable loss to evaluate the performance of neural networks. Continuous differentiability is defined as follows. Definition 1 (Continuously differentiable). We call a function f : Rn → R continuously differentiable with respect to the variable x if: (1) the function f is differentiable with respect to x; and (2) the gradient∇xf(x) of the function f is continuous with respect to the variable x.

heading: 3.2 MAIN RESULT
text: The theorem in this section relies on the following assumptions. Assumption 1. The training data cannot be fit by a 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 0.
To our best knowledge, our assumptions are the least restrictive compared with the relevant works in the literature. These assumptions are respectively justified as follows: (1) most real-world datasets are extremely complex and cannot be simply fit using linear models; (2) it is easy to 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|x|. Based on these four assumptions, we can prove the following theorem.
Theorem 1. 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.
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 Appendix A.1, 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-truth label and the prediction as follows.
l2 ( Yi, Ŷi ) = 1
2 ∥∥∥Yi − Ŷi∥∥∥2 F . (5)
Meanwhile, 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.
lce(Yi, Ŷi) = − dY∑ j=1 Yi,j log ( Ŷi,j∑dY k=1 Ŷi,k ) . (6)
One can also remove Assumption 4, if Assumption 3 is replaced by the following assumption, which is mildly more restrictive (see a detailed proof in pp. 34–37).
Assumption 5. The dimensions of the layers satisfy that:
d1 ≥ dY + 2, di ≥ dY + 1, i = 2, . . . , L− 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 on the loss surfaces of nonlinear neural networks, which however has a limited applicable domain (Choromanska et al., 2015; Swirszcz et al., 2016; Safran & Shamir, 2018; Yun et al., 2019b). A notable work by Yun et al. (2019b) proves that one-hidden-layer neural networks with two-piece linear (ReLU-like) activations for one-dimensional regression have infinitely many spurious local minima under squared loss. This work first constructs a 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 continuously differentiable loss.

heading: 3.3 PROOF SKELETON
text: This section presents the skeleton of the proof. Theorem 1 is proved in three stages. We first prove a simplified version of Theorem 1 and then extend the conditions in the last two stages. The proof is partially inspired by Yun et al. (2019b) but the proof in this paper has made nontrivial development and the results are significantly extended.
Yun et al. (2019b) and our paper both employ the following strategy: (a) construct a series of local minima based on a 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 are 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
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 a new separation lemma; and (3) From one-dimensional output to arbitrary-dimensional output: To prove the loss surface of a neural network with an arbitrary-dimensional output has an infinite number of spurious local minima, we need to deal with the calculus of functions whose domain 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.
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 Ỹ (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 a linear model. Therefore, the gradient ∇Ŷ R̂ of the empirical risk R̂ with respect to the prediction Ŷ is not zero. Suppose the i-th row of the gradient ∇Ŷ R̂ 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 implementations:
(a) We first construct a series of local minima of the empirical risk R̂ (see Appendix A.3, Lemma 5). The construction guarantees that every component of the output Ỹ (i) in each layer before the activations is positive, which secure all the input examples flow through the same part of the activations. Thereby, the nonlinear activations are reduced to 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 use several uniform scaling and translation operations to the outputs
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.

heading: 4 A BIG PICTURE OF THE LOSS SURFACE
text: This section draws a big picture for the loss surfaces of neural networks. Based on a 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.

heading: 4.1 PRELIMINARIES
text: The discussions in this section use the following concepts.
Definition 2 (Open ball and open set). The open ball in H centered at x ∈ H and of radius r > 0 is defined by B(h, r) = {x : ‖x − h‖ < r}. A subset A ⊂ H of a space H is called a open set, if for every point h ∈ A, there exists a positive real r > 0, such that the open ball B(h, r) with center h and radius r is in the subset A: B(h, r) ⊂ A. Definition 3 (Interior point and interior). For a subset A ⊂ H of a spaceH, a point h ∈ A is called an interior point of A, if there exists a positive real r > 0, such that the open ball B(h, r) with center h and radius r is in the subset A: B(h, r) ⊂ A. The set of all the interior points of the set A is called the interior of the set A.
Definition 4 (Limit point, closure, and boundary). For a subset A ⊂ H of a spaceH, a point h ∈ A is called a limit point, if for every r > 0, the open ball B(h, r) with center h and radius r contains some point of A: B(h, r)∩A 6= ∅. 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 5 (Multilinear). A function f : X1×X2 → Y is called multilinear if for arbitrary x11, x21 ∈ X , x12, x22 ∈ X2, and constants λ1, λ2, µ1, and µ2, we have
f(λ1x 1 1+λ2x 2 1, µ1x 1 2+µ2x 2 2) = λ1µ1f(x 1 1, x 1 2)+λ1µ2f(x 1 1, x 2 2)+λ2µ1f(x 2 1, x 1 2)+λ2µ2f(x 2 1, x 2 2).
Remark. The definition of “multilinear” implies that the domain of any multilinear function f is a connective and convex set, such as the smooth and multilinear cells below.
Definition 6 (Equivalence class, and quotient space). Suppose X is a linear space. [x] = {v ∈ X : v ∼ x} is an equivalence class, if there is an equivalent relation ∼ on [x], such that for any a, b, c ∈ [x], we have: (1) reflexivity: a ∼ a; (2) symmetry: if a ∼ b, b ∼ a; and (3) transitivity: if a ∼ b and b ∼ c, a ∼ c. The quotient space and quotient map are defined to be X/ ∼= {{v ∈ X : v ∼ x} : x ∈ X} and x→ [x], respectively.

heading: 4.2 MAIN RESULTS
text: In this section, the loss surface is defined under convex loss with respect to the prediction Ŷ 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 to 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.
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 are nondifferentiable.
Based on 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 3 (Equivalence classes of local minimum valleys). Suppose all conditions of Theorem 2 hold. Assume the loss function is strictly convex. Then, all local minima in a 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 1 (Quotient space of local minimum valleys). Suppose all conditions of Theorem 3 hold. There might exist some “parallel” local minimum valleys in the equivalence class of a local minimum 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 multilinear cell, when all activations are linear.

heading: 4.3 DISCUSSIONS AND PROOF TECHNIQUES
text: 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); 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 guarantees 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 surprising 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. Unfortunately, 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 is just equivalently multiplying a real constant to the output. However, the loss surface within a cell of a 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 R̂ with respect to Ŵ are also globally optimal in the cell. Every cell corresponds to a specific series of linear parts of the activations. Therefore, in any fixed cell, the activation hs−,s+ can be expressed by the slopes of the corresponding linear parts as the following equations,
R̂(W1,W2) = 1
n n∑ i=1 l (yi,W2h(W1xi)) = 1 n n∑ i=1 l (yi,W2diag (A·,i)W1xi) , (7)
where A·,i is the i-th column of matrix
A =  h ′ s−,s+((W1)1,·x1) · · · h ′ s−,s+((W1)1,·xn) ... . . .
... h′s−,s+((W1)d1,·x1) · · · h ′ s−,s+((W1)d1,·xn)  . Matrix A is constituted by collecting the slopes of the activation h at every point (W1)i,·xj .
Different elements of the matrix A can be multiplied either one of {s−, s+}. 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 as the product of a sequence of weight matrices. This difference ensures that the proofs of deep linear neural networks cannot be transplanted here.
Then, we prove that (see p. 40)
W2diag (A·,i)W1xi = AT·,idiag(W2)W1xi. (8)
Applying eq. (8) to eq. (7), the empirical risk R̂ equals to a formulation similar to the linear neural networks,
R̂ = 1 n n∑ i=1 l ( yi −AT·,idiag(W2)W1xi ) . (9)
Afterwards, define Ŵ1 = diag(W2)W1 and then straighten the matrix Ŵ1 to a vector Ŵ , Ŵ = ( (Ŵ1)1,· · · · (Ŵ1)d1,· ) ,
Define Q : (W1,W2) 7→ Ŵ , and also define,
X̂ = (A·,1 ⊗ x1 · · · A·,n ⊗ xn) .
We can prove the following equations (see p. 41),( AT·,1Ŵ1x1 · · · AT·,nŴ1xn ) =Ŵ X̂.
Applying eq. (9), the empirical risk is transferred to a convex function as follows,
R̂ = 1 n n∑ i=1 l ( yi, (A·,i) T Ŵ1xi ) = 1 n n∑ i=1 l(yi, Ŵ X̂i).
We then prove that the local optimality of the empirical risk R̂ is maintained when the weightsW are 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 is not surprising but the proof is technically non-trivial (see a detailed proof in pp. 42-43).
Equivalence classes and quotient space of local minimum valleys. The constructed mappingQ is a quotient map. Under the setting in the previous property, all local minima in a cell is an equivalence class; they are concentrated as a local minimum valley. However, there might exist some “parallel” local minimum valley in 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-based methods are connected by a path in the parameter space with almost constant empirical risk, which is proposed in two empirical works (Garipov et al., 2018; Draxler et al., 2018). A recent theoretical work (Kuditipudi et al., 2019) proves that dropout stability and noise stability guarantee the mode connectivity.
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-differentiable 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 are equally good, and also, they are all global minima as follows. This result unites the existing results on linear neural networks (Kawaguchi, 2016; Baldi & Hornik, 1989; Lu & Kawaguchi, 2017; Freeman & Bruna, 2017; Zhou & Liang, 2018; Laurent & von Brecht, 2018; Yun et al., 2018).

heading: 5 CONCLUSION AND FUTURE DIRECTIONS
text: 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-entropy 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 0. Second, based on a recent result that the loss surface has a smooth and multilinear partition, we draw a 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 onehidden-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 a 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 as follows,
• Investigate the (potential) equivalence classes and quotient space of local minimum valleys for deep neural networks. This paper suggests a 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 a 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 a strategy that treats every local minimum valley as a whole. However, the sophisticated local geometrical properties around the local minimum valleys are still premature, such as the sharpness/flatness of the local minima, the potential categorization 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 results have overwhelmingly suggested that deep learning has excellent optimization and generalization capabilities, which is, however, beyond the current theoretical understanding: (1) one can employ stochastic convex optimization methods (such as SGD) to minimize 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) heavily-parametrized neural networks can generalize well in many tasks, which is beyond the expectation of most current theoretical frameworks based on hypothesis complexity and the variants. The sophisticated geometrical expression, if fortunately, we possess in the future, would be a compelling push to tackle the generalization and optimization muses of deep learning.

heading: ACKNOWLEDGMENTS
text: This work was supported by Australian Research Council Project FL-170100117. The authors sincerely appreciate Micah Goldblum and the anonymous reviewers for their constructive comments.

heading: A PROOF OF THEOREM 1
text: This appendix gives a detailed proof of Theorem 1 omitted from the main text. It follows the skeleton presented in Section 3.3.

heading: A.1 SQUARED LOSS AND CROSS-ENTROPY LOSS
text: 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 to zero when the prediction and the label are different.
Proof. Apparently, the squared loss is differentiable with respect to Ŷ . Specifically, the gradient with respect to Ŷ is as follows,
∇Ŷ ∥∥∥Y − Ŷ ∥∥∥2 = 2(Y − Ŷ ) ,
which is continuous with respect to Ŷ .
Also, when the prediction Ŷ does not equals to the label Y , we have ∇Ŷ ∥∥∥Y − Ŷ ∥∥∥2 6= 0.
The proof is completed.
Lemma 3. The cross-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 ∈ [1 : n], the cross-entropy loss is differentiable with respect to Ŷi. The j-th component of the gradient with respect to the prediction Ŷi is as follows,
∂ ( −
dY∑ k=1 Yk,i log ( eŶk,i∑dY k=1 e Ŷk,i )) ∂Ŷj,i = ( dY∑ k=1 Yk,i ) eŶj,i
dY∑ k=1 eŶk,i − Yj,i. (10)
which is continuous with respect to Ŷi. So, the cross-entropy loss is continuously differentiable with respect to Ŷi.
Additionally, if the gradient (eq. (10)) is zero, we have the following equations,( dY∑ k=1 Yk,i ) eŶj,i − Yj,i dY∑ k=1 eŶk,i = 0, j = 1, 2, · · · , n.
Rewrite it into the matrix form, we have dY∑ k=1 Yk,i − Y1,i −Y1,i · · · −Y1,i −Y2,i dY∑ k=1 Yk,i − Y2,i · · · −Y2,i ... ... . . . ...
−YdY ,i · · · −YdY ,i dY∑ i=1 Yk,i − YdY ,i
  eŶ1,i eŶ2,i ... eŶdY ,i  = 0.
Since dY∑ k=1 Yk,i = 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 dY∑ k=1 Yk,i − Y1,i −Y1,i · · · −Y1,i −Y2,i dY∑ k=1 Yk,i − Y2,i · · · −Y2,i ... ... . . . ...
−YdY ,i · · · −YdY ,i dY∑ i=1 Yk,i − YdY ,i
  Y1,i Y2,i ... YdY ,i  = 0.
Therefore, 0 6= eŶk,i = λYk,i, for some λ ∈ R, which contradicts to the assumption that some of the components of Y is 0 (Yi,· is a one-hot vector).
The proof is completed.
A.2 STAGE (1)
In Stage (1), we prove that deep neural networks with one hidden layer, two-piece linear activation hs−,s+ , 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 a set of parameters with smaller empirical risk.
Without loss of generality, we assume that s+ 6= 0. Otherwise, suppose that s+ = 0. From the definition of ReLU-like activation (eq. (4)), we have s− 6= 0. Since
hs−,s+(x) = h−s+,−s−(−x), the output of the neural network with parameters {
[Wi] L i=1 , [bi] L i=1 } and activation hs−,s+ equals
to that of the neural network with parameters {
[W ′i ] L i=1 , [b ′ i] L i=1 } and activation h−s+,−s− where
W ′i = −Wi, b′i = −bi, i = 1, 2, · · · , L− 1 and W ′L = WL, b′L = bL. Since { [Wi] L i=1 , [bi] L i=1 } →{
[W ′i ] L i=1 , [b ′ i] L i=1
} is an one-to-one map, it is equivalent to consider either the two networks, with
h−s+,−s−(x) has non-zero slope when x > 0.
Step (a). Construct local minima of the loss surface. Lemma 4. Suppose that W̃ is a local minimizer of
f(W ) 4 = 1
n n∑ i=1 l ( Yi,W [ xi 1 ]) , (11)
Under Assumption 3, any one-hidden-layer neural network has a local minimum at
Ŵ1 = [ [ W̃ ] ·,[1:dX ]
0(d1−dY )×dX
] , b̂1 = [ [ W̃ ] ·,dX+1
− η1dY −η1d1−dY
] , (12)
and Ŵ2 = [ 1 s+ IdY 0dY ×(d1−dY ) ] , b̂2 = η1dY , (13)
where Ŵ1 and b̂1 are respectively the weight matrix and the bias of the first layer, Ŵ2 and b̂2 are respectively the weight matrix and the bias of the second layer, and η is a negative constant with absolute value sufficiently large such that
W̃ X̃ − η1dY 1Tn > 0, (14) where > is element-wise.
Also, the loss in this lemma is continuously differentiable loss whose gradient does not equals to 0 when the prediction is not the same as the ground-truth label.
Proof. We show that the empirical risk is higher in the neiborhood of {[ Ŵi ]2 i=1 , [ b̂i ]2 i=1 } , in order
to prove that {[ Ŵi ]2 i=1 , [ b̂i ]2 i=1 } is a local minimizer.
The output of the first layer before the activation is
Ỹ (1) = Ŵ1X + b̂11 T n = [ ŴX − η1dY 1Tn −η1d1−dY 1Tn ] .
Because η is a negative constant with absolute value sufficiently large such that eq. (27)) holds, the output above is positive (element-wise), the output of the neural network with parameters {Ŵ1, Ŵ2, b̂1, b̂2} is
Ŷ =Ŵ2hs−,s+ ( Ŵ1X + b̂11 T n ) + b̂21 T n
=s+Ŵ2 ( Ŵ1X + b̂11 T n ) + b̂21 T n
=s+ [ 1 s+ IdY 0dY ×(d1−dY ) ] [ ŴX − η1dY 1Tn −η1d1−dY 1Tn ] + η1dY 1 T n
=W̃ X̃,
where X̃ is defined as
X̃ = [ X 1Tn ] . (15)
Therefore, the empirical risk R̂ in terms of parameters {Ŵ1, Ŵ2, b̂1, b̂2} is
R̂ ( Ŵ1, Ŵ2, b̂1, b̂2 ) = 1
n n∑ i=1 l ( Yi, ( W̃ X̃ ) ·,i ) = 1 n n∑ i=1 l ( Yi, W̃ [ xi 1 ]) = f(W̃ ).
Then, we introduce a sufficiently small disturbance {
[δWi] 2 i=1 , [δbi] 2 i=1 } into the parameters{[
Ŵi ]2 i=1 , [ b̂i ]2 i=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
Ŷ ([ Ŵi + δWi ]2 i=1 , [ b̂i + δbi ]2 i=1 ) = ( Ŵ2 + δW2 ) hs−,s+ (( Ŵ1 + δW1 ) X + ( b̂1 + δb1 ) 1Tn ) + ( b̂2 + δb2 ) 1Tn
(∗) = ( Ŵ2 + δW2 ) s+ (( Ŵ1 + δW1 ) X + ( b̂1 + δb1 ) 1Tn ) + ( b̂2 + δb2 ) 1Tn
=s+δW2 (( Ŵ1 + δW1 ) X + ( b̂1 + δb1 ) 1Tn ) + s+Ŵ2δW1X + s+Ŵ2δb11 T n + δb21 T n
+ Ŵ2s+(Ŵ1X + b̂11 T n ) + b̂21 T n = ( s+δW2 ( Ŵ1 + δW1 ) + s+Ŵ2δW1 ) X + ( s+Ŵ2δb1 + δb2 + s+δW2 ( b̂1 + δb1 )) 1Tn
+ Ŵ2hs−,s+(Ŵ1X + b̂11 T n ) + b̂21 T n
=(W̃ + δ) [ X 1Tn ] ,
where eq. (∗) is because all components of ( Ŵ1 + δW1 ) X + (b′1 + δb1)1 T n are positive, and δ is
defined as the following matrix δ = [ s+ ( Ŵ2δW1 + δW2Ŵ1 + δW2δW1 ) s+Ŵ2δb1 + δb2 + s+δW2 ( b̂1 + δb1 )] .
Therefore, the empirical risk R̂ with respect to {[ Ŵi + δWi ]2 i=1 , [ b̂i + δbi ]2 i=1 } is
R̂ ([ Ŵi + δWi ]2 i=1 , [ b̂i + δbi ]2 i=1 ) = 1 n n∑ i=1 l ( Yi, (( W̃ + δ ) X̃ ) ·,i )
= 1
n n∑ i=1 l ( Yi, ( W̃ + δ )[ xi 1 ]) = f(W̃ + δ).
δ approaches zero when the disturbances {δW1, δW2, δb1, δb2} approach zero (element-wise). Since Ŵ is the local minimizer of f(W ), we have
R̂ ([ Ŵi ]2 i=1 , [ b̂i ]2 i=1 ) = f(Ŵ ) ≤ f(Ŵ + δ) = R̂ ([ Ŵi + δWi ]2 i=1 , [ b̂i + δbi ]2 i=1 ) . (16)
Because the disturbances {δW1, δW2, δb1, δb2} are arbitrary, eq. (16) demonstrates that{[ Ŵi ]2 i=1 , [ b̂i ]2 i=1 } is a local minimizer.
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 4 are spurious.
Proof. The minimizer W̃ is the solution of the following equation
∇W f(W ) = 0.
Specifically, we have ∂f ( W̃ )
∂Wi,j = 0, i ∈ {1, · · · , dY }, j ∈ {1, · · · , dX},
Applying the definition of f(W ) (eq. (11)), ∂f ( W̃ )
∂Wk,j = n∑ i=1 ∇Ŷi l ( Yi, W̃ [ xi 1 ]) Ek,j [ xi 1 ] = n∑ i=1 ( ∇Ŷi l ( Yi, W̃ [ xi 1 ])) k ([ xi 1 ]) j ,
where Ŷi = W̃ [ xi 1 ] ,∇Ŷi l ( Yi, W̃ [ xi 1 ]) ∈ R1×dY . Since k, j are arbitrary in {1, · · · , dY } and
{1, · · · , dX}, respectively, we have
V [ XT 1n ] = 0, (17)
where
V = [( ∇Ŷ1 l ( Y1, W̃ [ x1 1 ]))T · · · ( ∇Ŷn l ( Yn, W̃ [ xn 1 ]))T] .
We then define Ỹ = W̃ X̃ . Applying Assumption 1, we have Ỹ − Y = ( W̃ X̃ − Y ) 6= 0,
Thus, there exists some k-th row of Ỹ − Y that does not equal to 0.
We can rearrange the rows of W̃ and Y simultaneously, while W̃ is maintained as the local minimizer of f(W ) and f(W̃ ) invariant1. Without loss of generality, we assume k = 1 (k is the index of the row). Set u = V1,· and vi = Ỹ1,i in Lemma 7. There exists a non-empty separation I = [1 : l′] and J = [l′ + 1 : n] of S = {1, 2, · · · , n} and a vector β ∈ RdX , such that
(1.1) for any positive constant α small enough, and i ∈ I , j ∈ J , Ỹ1,i − αβTxi < Ỹ1,j − αβTxj ; (1.2) ∑ i∈I V1,i 6= 0.
Define
η1 = Ỹ1,l′ − αβTxl′ + 1
2
( min
i∈{l′+1,...,n}
( Ỹ1,i − αβTxi ) − ( Ỹ1,l′ − αβTxl′ )) .
Applying (1.1), for any i ∈ I
Ỹ1,i − αβTxi − η1 = ( Ỹ1,i − αβTxi − Ỹ1,l′ + αβTxl′ ) − 1
2
( min
i∈{l′+1,...,n}
( Ỹ1,i − αβTxi ) − ( Ỹ1,l′ − αβTxl′ )) <0,
while for any j ∈ J ,
Ỹ1,j − αβTxj − η1 > 0 = ( Ỹ1,j − αβTxi − Ỹ1,l′ + αβTxl′ ) − 1
2
( min
i∈{l′+1,...,n}
( Ỹ1,i − αβTxi ) − ( Ỹ1,l′ − αβTxl′ )) ≥1
2
( min
i∈{l′+1,...,n}
( Ỹ1,i − αβTxi ) − ( Ỹ1,l′ − αβTxl′ )) >0.
Define γ ∈ R which satisfies
|γ| =  1 2 min i∈{l′+1,...,st+1} αβT (xl − xi), l′ < st+1
α, l′ = st+1
,
where st+1 is defined in Lemma 7.
We argue that ∣∣∣∣12 ( min i∈{l′+1,...,n} ( Ỹ1,i − αβTxi ) − ( Ỹ1,l′ − αβTxl′ ))∣∣∣∣− |γ| > 0. (18) When l′ = st+1, eq. (58) stands. Also,
lim α→0+ γ = 0,
lim α→0+
( min
i∈{l′+1,...,n}
( Ỹ1,i − αβTxi ) − ( Ỹ1,l′ − αβTxl′ )) = min i∈{l′+1,...,n} Ỹ1,i − Ỹ1,l′ > 0.
Therefore, we get eq. (18) when α is small enough.
When l′ < st+1, eq. (57) stands. Therefore,
|γ| = 1 2 ∣∣∣∣12 ( min i∈{l′+1,...,n} ( Ỹ1,i − αβTxi ) − ( Ỹ1,l′ − αβTxl′ ))∣∣∣∣ , which apparently leads to eq. (18).
1f is also the function in term of Y .
Therefore, for any i ∈ I , we have that
Ỹ1,i − αβTxi − η1 + |γ|
≤ − 1 2
( min
i∈{l′+1,...,n}
( Ỹ1,i − αβTxi ) − ( Ỹ1,l′ − αβTxl′ )) + |γ|
<0,
while for any j ∈ J ,
Ỹ1,j − αβTxj − η1 − |γ|
≥1 2
( min
i∈{l′+1,...,n}
( Ỹ1,i − αβTxi ) − ( Ỹ1,l′ − αβTxl′ )) − |γ|
>0.
Furthermore, define ηi (2 ≤ i ≤ dY ) as negative reals with absolute value sufficiently large, such that for any i ∈ [2 : dY ] and any j ∈ [1 : n],
Ỹi,j − ηi > 0.
Now we construct a point in the parameter space whose empirical risk is smaller than the proposed local minimum in Lemma 4 as follows
W̃1 =  W̃1,[1:dX ] − αβT −W̃1,[1:dX ] + αβT W̃2,[1:dX ] ...
W̃dY ,[1:dX ] 0(d1−dY −1)×dX
 , (19)
b̃1 =  W̃1,[dX+1] − η1 + γ −W̃1,[dX+1] + η1 + γ W̃2,[dX+1] − η2
... W̃dY ,[dX+1] − ηdY
0(d1−dY −1)×1
 , (20)
W̃2 =  1 s++s− − 1s++s− 0 0 · · · 0 0 · · · 0 0 0 1s+ · · · 0 ... ... ... ... ... ... 1s+ · · · 0 . . . ... ... ... ... . . . ... ... ...
0 0 0 0 · · · 1s+ 0 · · · 0
 , (21)
and
b̃2 =  η1 η2 ...
ηdY  , (22) where W̃i and b̃i are the weight matrix and the bias of the i-th layer, respectively.
After some calculations, the network output of the first layer before the activation in terms of{[ W̃i ]2 i=1 , [ b̃i ]2 i=1 } is
Ỹ (1) = W̃1X + b̃11 T n =  W̃1,·X̃ − αβTX − η11Tn + γ1Tn −W̃1,·X̃ + αβTX + η11Tn + γ1Tn W̃2,·X̃ − η21Tn ...
W̃dY ,·X̃ − ηdY 1Tn 0(d1−dY −1)×n
 .
Therefore, the output of the whole neural network is
Ŷ = W̃2hs−,s+ ( W̃1X + b̃11 T n ) + b̃21 T n
= W̃2hs−,s+   W̃1,·X̃ − αβTX − η11Tn + γ1Tn −W̃1,·X̃ + αβTX + η11Tn + γ1Tn W̃2,·X̃ − η21Tn ...
W̃dY ,·X̃ − ηdY 1Tn 0(d1−dY −1)×n
  + b̃21 T n .
Specifically, if j ≤ l′,( Ỹ (1) ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 )) 1,j =W̃1,· [ xj 1 ] − αβTxj − η1 + γ
=Ỹ1,j − αβTxj − η1 + γ < 0,( Ỹ (1) ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 )) 2,j =− W̃1,· [ xj 1 ] + αβTxj + η1 + γ
=− Ỹ1,j + αβTxj + η1 + γ > 0. Therefore, (1, j)-th component of Ŷ ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 ) is(
Ŷ ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 )) 1,j
= (
1 s++s− ,− 1s++s− , 0, · · · , 0 ) hs−,s+   W̃1,·X − αβTX − η11Tn + γ1Tn −W̃1,·X + αβTX + η11Tn + γ1Tn W̃2,·X − η21Tn ...
W̃dY ,·X − ηdY 1Tn 0d1−dY −11 T n
  ·,j
+ η1
= 1
s+ + s− hs−,s+(Ỹ1,j − αβTxj − η1 + γ)−
1
s+ + s− hs−,s+(−Ỹ1,j + αβTxj + η1 + γ)
+ η1
= s−
s+ + s− (Ỹ1,j − αβTxj − η1 + γ)− s+ s+ + s− (−Ỹ1,j + αβTxj + η1 + γ)
+ η1
=Ỹ1,j − αβTxj + s− − s+ s+ + s− γ; (23)
Similarly, when j > l′, the (1, j)-th component is( Ŷ ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 )) 1,j
= s+
s+ + s− (Ỹ1,j − αβTxj − η1 + γ)− s− s+ + s− (−Ỹ1,j + αβTxj + η1 + γ) + η1
=Ỹ1,j − αβTxj + s+ − s− s+ + s− γ, (24)
and ( Ŷ ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 )) i,j = s+ s+ (Ỹi,j − ηi) + ηi = Ỹi,j , i ≥ 2. (25)
Thus, the empirical risk of the neural network with parameters {[ W̃i ]2 i=1 , [ b̃i ]2 i=1 } is
R̂ ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 ) = 1
n n∑ i=1 l ( Yi, W̃2 ( W̃1xi + b̃11 T n ) + b̃21 T n ) = 1
n n∑ i=1 ( l ( Yi, W̃ [ xi 1 ]) +∇Ŷi l ( Yi, W̃ [ xi 1 ])( W̃2 ( W̃1xi + b̃11 T n ) + b̃21 T n − W̃ [ xi 1 ]))
+ n∑ i=1 o (∥∥∥∥W̃2 (W̃1xi + b̃11Tn)+ b̃21Tn − W̃ [xi1 ]∥∥∥∥) . (26)
Applying eqs. (23), (24), and (25), we have
n∑ i=1 ( W̃2 ( W̃1xi + b̃1 ) + b̃2 − W̃ [ xi 1 ])T ∇Ŷi l ( Yi, W̃ [ xi 1 ])T (∗) =
l′∑ i=1 V1,i(−αβTxi + s+ − s− s+ + s− γ) + n∑ i=l′+1 V1,i(−αβTxi − s+ − s− s+ + s− γ)
=2γ l′∑ i=1 s+ − s− s+ + s− V1,i,
where eq. (∗) is because
( W̃2 ( W̃1xi + b̃1 ) + b̃2 − W̃ [ xi 1 ]) j =  − αβTxj + s− − s+ s+ + s− γ, j = 1, i ≤ l′ − αβTxj − s− − s+ s+ + s− γ, j = 1, i > l′
0, j ≥ 2
.
Furthermore, note that α = O(γ) (from the definition of γ). We have
n∑ i=1 o (∥∥∥∥W̃2 (W̃1xi + b̃1)+ b̃2 − Ŵ [xi1 ]∥∥∥∥)
= n∑ i=1 o √√√√ n∑ j=1 ( W̃2 ( W̃1xi + b̃1 ) + b̃2 − W̃ [ xi 1 ])2 j  =o(γ).
Let α be sufficiently small while sgn(γ) = −sgn ( l′∑ i=1 s+−s− s++s− V1,i ) . We have
n∑ i=1 l ( Yi, W̃2 ( W̃1xi + b̃1 ) + b̃2 ) − n∑ i=1 l ( Yi, Ŵ [ xi 1 ])
=2γ l′∑ i=1 s+ − s− s+ + s− V1,i + o(γ)
(∗∗) < 0,
where inequality (∗∗) comes from (1.2) (see p. 18). From Lemma 4, there exists a local minimizer {[ Ŵi ]2 i=1 , [ b̂i ]2 i=1 } with empirical risk that equals
to f(W̃ ). Meanwhile, we just construct a point in the parameter space with empirical risk smaller than f(W̃ ).
Therefore, {[ Ŵi ]2 i=1 , [ b̂i ]2 i=1 } is a 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 hs−,s+ have spurious local minima. Here, we still assume s+ 6= 0. We have justified this assumption in Stage (1).
This stage is organized similarly with Stage (1): (a) Lemma 5 constructs a local minimum; and (b) Theorem 5 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 − 1 hidden layers. Then, this network has a local minimum at
Ŵ ′1 = [ [ W̃ ] ·,[1:dX ]
0(d1−dY )×dX
] , b̂′1 = [ [ W̃ ] ·,dX+1
− η1dY −η1d1−dY
] ,
Ŵ ′i = 1
s+ dY∑ j=1 Ej,j + 1 s+ di∑ j=dY +1 Ej,(dY +1), b̂ ′ i = 0 (i = 2, 3, ..., L− 1),
and Ŵ ′L = [ 1 s+ IdY 0dY ×(dL−1−dY ) ] , b̂′L = η1dY ,
where Ŵ ′i and b̂ ′ i are the weight matrix and the bias of the i-th layer, respectively, and η is a negative constant with absolute value sufficiently large such that
W̃ X̃ − η1dY 1Tn > 0, (27)
where > is element-wise.
Proof. Recall the discussion in Lemma 4 that all components of Ŵ1X + b̂11Tn are positive. Specifically,
Ŵ1X + b̂11 T n =  Ỹ − η1dY 1Tn −η1d1−dY 1Tn  , where Ỹ is defined in Lemma 4.
Similar to the discussions in Lemma 4, when the parameters equal to {[ Ŵ ′i ]L i=1 , [ b̂′i ]L i=1 } , the output of the first layer before the activation function is
Ỹ (1) = Ŵ ′1X + b̂ ′ 11 T n =  Ỹ − η1dY 1Tn −η1d1−dY 1Tn  , and
Ỹ − η1dY 1Tn > 0, (28) −η1d1−dY 1Tn > 0. (29)
Here > is defined element-wise.
After the activation function, the output of the first layer is
Y (1) = hs−,s+(Ŵ ′ 1X + b̂ ′ 11 T n ) = s+(Ŵ ′ 1X + b̂ ′ 11 T n ) = s+  Ỹ − η1dY 1Tn −η1d1−dY 1Tn  . We prove by induction that for all i ∈ [1 : L− 1] that
Ỹ (i) > 0 , element-wise, (30)
Y (i) = s+ Ỹ − η1dY 1Tn −η1di−dY 1Tn  . (31) Suppose that for 1 ≤ k ≤ L− 2, Ỹ (k) is positive (element-wise) and
Y (k) = s+  Ỹ − η1dY 1Tn −η1dk−dY 1Tn  . Then the output of the (k + 1)-th layer before the activation is
Ỹ (k+1) = Ŵ ′k+1Y (k) + b̂′k+11 T n
= 1
s+  dY∑ j=1 Ej,j + dk+1∑ j=dY +1 Ej,(dY +1)  s+  Ỹ − η1dY 1Tn −η1dk−dY 1Tn  =
 Ỹ − η1dY 1Tn −η1dk+1−dY 1Tn  . Applying eqs. (28) and (29), we have
Ỹ (k+1) =  Ỹ − η1dY 1Tn −η1dk+1−dY 1Tn  > 0, where > is defined element-wise. Therefore,
Y (k+1) = hs−,s+
( Ỹ (k+1) ) = s+Ỹ (k+1) = s+  Ỹ − η1dY 1Tn −η1dk+1−dY 1Tn  . We thereby prove eqs. (30) and (31).
Therefore, Y (L) can be calculated as Ŷ = Y (L) = Ŵ ′LY (L−1) + b̂′L1 T n
= 1
s+
[ IdY 0dY ×(dL−1−dY ) ] s+ Ỹ − η1dY 1Tn −η1di−dY 1Tn + η1dY 1Tn = Ỹ . (32)
Then, we show the empirical risk is higher around {[ Ŵ ′i ]L i=1 , [ b̂′i ]L i=1 } in order to prove that{[
Ŵ ′i ]L i=1 , [ b̂′i ]L i=1 } is a local minimizer.
Let {[ Ŵ ′i + δ ′ Wi ]L i=1 , [ b̂′i + δ ′ bi ]L i=1 } be point in the parameter space which is close enough to the
point {[ Ŵ ′i ]L i=1 , [ b̂′i ]L i=1 } . Since the disturbances δ′Wi and δ ′ bi are both close to 0 (element-wise),
all components of Ỹ (i) ([ Ŵ ′i + δ ′ Wi ]L i=1 , [ b̂′i + δ ′ bi ]L i=1 ) remains positive. Therefore, the output
of the neural network in terms of parameters {[ Ŵ ′i + δ ′ Wi ]L i=1 , [ b̂′i + δ ′ bi ]L i=1 } is
Ŷ ([ Ŵ ′i + δ ′ Wi ]L i=1 , [ b̂′i + δ ′ bi ]L i=1 ) =(Ŵ ′L + δ ′ WL)hs−,s+ ( . . . hs−,s+ (( Ŵ ′1 + δ ′ W1 ) X + ( b̂′1 + δ ′ b1 ) 1Tn ) . . . )
+ ( b̂′L + δ ′ bL ) 1Tn
=(Ŵ ′L + δ ′ WL)s+ ( . . . s+ (( Ŵ ′1 + δ ′ W1 ) X + ( b̂′1 + δ ′ b1 ) 1Tn ) . . . )
+ ( b̂′L + δ ′ bL ) 1Tn
=M1X +M21 T n , where M1 and M2 can be obtained from {[ Ŵ ′i ]L i=1 , [ b̂′i ]L i=1 } and { [δ′Wi] L i=1 , [δ ′ bi] L i=1 } through several multiplication and summation operations2.
Rewrite the output as
M1X +M21 T n = [M1 M2] [ X 1Tn ] .
Therefore, the empirical risk R̂ before and after the disturbance can be expressed as f(W̃ ) and f ([M1 M2]), respectively.
When the disturbances {
[δ′Wi] L i=1 , [δ ′ bi] L i=1 } approach 0 (element-wise), [M1 M2] approaches W̃ .
Therefore, when {
[δ′Wi] L i=1 , [δ ′ bi] L i=1
} are all small enough, we have
R̂ ([ Ŵ ′i + δ ′ Wi ]L i=1 , [ b̂′i + δ ′ bi ]L i=1 ) =f([M1 M2])
≥f(W̃ ) =R̂ ([ Ŵ ′i ]L i=1 , [ b̂′i ]L i=1 ) . (33)
Since {[ Ŵ ′i + δ ′ Wi ]L i=1 , [ b̂′i + δ ′ bi ]L i=1 } are arbitrary within a sufficiently small neighbour of{[
Ŵ ′i ]L i=1 , [ b̂′i ]L i=1 } , eq. (33) yields that {[ Ŵ ′i ]2 i=1 , [ b̂′i ]2 i=1 } is a local minimizer.
Step (b). Prove the constructed local minima are spurious. 2Since the exact form of M1 and M2 are not needed, we omit the exact formulations here.
Theorem 5. Under the same conditions of Lemma 5 and Assumptions 1, 2, and 4, the constructed spurious local minima in Lemma 5 are spurious.
Proof. We first construct the weight matrix and bias of the i-th layer as follows,
W̃ ′1 = W̃1, b̃ ′ 1 = b̃1,
W̃ ′2 =
[ W̃2
0(d2−dY )×d1
] , b̃′2 = λ1d2 + [ b̃2
0(d2−dY )×1
] ,
W̃ ′i = 1
s+ dY∑ i=1 Ei,i, b̃ ′ i = 0 (i = 3, 4, ..., L− 1),
and
W̃ ′L = 1
s+ dY∑ i=1 Ei,i, b̃ ′ L = −λ1dY ,
where W̃1, W̃2, b̃1 and b̃2 are defined by eqs. (19), (20), (21), and (22), respectively, and λ is a sufficiently large positive real such that
Ŷ ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 ) + λ1d21 T n > 0, (34)
where > is defined element-wise. We argue that {[ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 } corresponds to a smaller empirical risk than f(W̃ ) which is defined in Lemma 4.
First, Theorem 4 has proved that the point { W̃1, W̃2, b̃1, b̃2 } corresponds to a smaller empirical risk
than f(W̃ ).
We prove by induction that for any i ∈ {3, 4, ..., L− 1},
Ỹ (i) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) ≥ 0 , element-wise, (35)
Y (i) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) = s+ Ŷ ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 ) + λ1dY 1 T n
0(di−dY )×n  . (36) Apparently the output of the first layer before the activation is
Ỹ (1) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) = W̃ ′1X + b̃ ′ 11 T n = W̃1X + b̃11 T n = Ỹ (1) ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 ) .
Therefore, the output of the first layer after the activation is
Y (1) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) =hs−,s+ ( Ỹ (1) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 )) =hs−,s+ ( Ỹ (1) ([ W̃i ]L i=1 , [ b̃i ]L i=1
)) =Y (1) ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 ) .
Thus, the output of the second layer before the activation is Ỹ (2) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) =W̃ ′2Y (1) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) + b̃′21 T n
=
[ W̃2
0(d2−dY )×d1
] Y (1) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) + [ b̃2
0(d2−dY )×1
] 1Tn
+ λ1d21 T n
= Ŷ ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 ) + λ1dY 1 T n
λ1d2−dY 1 T n  . Applying the definition of λ (eq. (34)),
Ỹ (2) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) > 0 , element-wise. (37)
Therefore, the output of the second layer after the activation is Y (2) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) = hs−,s+ ( Ỹ (2) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ))
= s+ Ŷ ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 ) + λ1dY 1 T n
λ1d2−dY 1 T n
 .
Meanwhile, the output of the third layer before the activation is Ỹ (3) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) can be
calculated based on Y (2) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) :
Ỹ (3) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) = W̃ ′3Y (2) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) + b̃′31 T n
= 1
s+ ( dY∑ i=1 Ei,i ) s+ Ŷ ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 ) + λ1dY 1 T n
λ1d2−dY 1 T n

= Ŷ ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 ) + λ1dY 1 T n
0(d3−dY )×n  . Applying eq. (37),
Ỹ (3) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) ≥ 0 , element-wise. (38)
Therefore, the output of the third layer after the activation is Y (3) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) = hs−,s+ ( Ỹ (3) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 )) = s+ ( Ỹ (3) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ))
= s+ Ŷ ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 ) + λ1dY 1 T n
0(d3−dY )×n
 .
Suppose eqs. (35) and (36) hold for k (3 ≤ k ≤ L− 2), when k + 1, Ỹ (k+1) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) = W̃ ′k+1Y (k) ([ W̃ ′i ]2 i=1 , [ b̃′i ]2 i=1 ) + b̃′k+11 T n
= 1
s+ ( dY∑ i=1 Ei,i ) s+ Ŷ ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 ) + λ1dY 1 T n
0(dk−dY )×n

= Ŷ ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 ) + λ1dY 1 T n
0(dk+1−dY )×n  . Applying eq. (38),
Ỹ (k+1) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) ≥ 0 , element-wise. (39)
Therefore, the output of the (k + 1)-th layer after the activation is Y (k+1) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) =hs−,s+ ( Ỹ (k+1) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 )) =s+Ỹ (k+1) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 )
=s+ Ŷ ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 ) + λ1dY 1 T n
0(dk+1−dY )×n  . Therefore, eqs. (35) and (36) hold for any i ∈ {3, 4, ..., L− 1}. Finally, the output of the network is
Ŷ ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) =Y (L) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) =W̃ ′LY (L−1) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) + b̃′L1 T n
=
( 1
s+ dY∑ i=1 Ei,i
) s+ Ŷ ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 ) + λ1dY 1 T n
0(dL−1−dY )×n  − λ1dY 1Tn
=Ŷ ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 ) .
Applying Theorem 4, we have R̂ ([ W̃ ′i ]L i=1 , [ W̃ ′i ]L i=1 ) = R̂ ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 ) < f(W̃ ).
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.
Lemma 6. Suppose t is a non-differentiable point for the piece-wise linear activation function h and σ is a constant such that the activation h is differentiable in the intervals (t − σ, t) and (t, t + σ). Assume that M is a sufficiently large positive real such that
1
M ∥∥∥Ŵ ′1X + b̂′11Tn∥∥∥ F < σ. (40)
Let αi be any positive real such that
α1 = 1
0 < αi < 1, i = 2, · · · , L− 1. (41) Then, under Assumption 3, any neural network with piecewise linear activations and L − 1 hidden layers has local minima at
Ŵ ′′1 = 1
M Ŵ ′1, b̂ ′′ 1 =
1
M b̂′1 + t1d1 ,
Ŵ ′′i = αiŴ ′ i , b̂ ′′ i = −αiŴ ′ih(t)1di−1 + t1di +
Πij=2αj
M b̂′i, (i = 2, 3, ..., L− 1),
and Ŵ ′′L =
1
ΠLj=2αj MŴ ′L, b̂ ′′ L = − M∏L−1 j=2 αj Ŵ ′Lh(t)1dL−1 + b̂ ′ L
where {[ Ŵ ′i ]L i=1 , [ b̂′i ]L i=1 } is the local minimizer constructed in Lemma 5. Also, the loss is con-
tinuously differentiable, whose derivative with respect to the prediction Ŷi may equal to 0 only when the prediction Ŷi and label Yi are the same.
Proof. Define s− = lim θ→0− h′(θ) and s+ = lim θ→0+ h′(θ).
We then prove by induction that for all i ∈ [1 : L−1], all components of the i-th layer output before the activation Ỹ (i) ([ Ŵ ′′i ]L i=1 , [ b̂′′i ]L i=1 ) are in interval (t, t+ σ), and
Y (i) ([ Ŵ ′′i ]L i=1 , [ b̂′′i ]L i=1 ) = h(t)1di1 T n + Πij=1αj M Y (i) ([ Ŵ ′i ]L i=1 , [ b̂′i ]L i=1 ) .
The first layer output before the activation is, Ỹ (1) ([ Ŵ ′′i ]L i=1 , [ b̂′′i ]L i=1 ) = Ŵ ′′1 X + b̂ ′′ 11 T n = 1 M Ŵ ′1X + 1 M b̂′11 T n + t1d11 T n . (42)
We proved in Lemma 5 that Ŵ ′1X + b̂ ′ 11 T n is positive (element-wise). Since the Frobenius norm of a matrix is no smaller than any component’s absolute value, applying eq. (40), we have that for all i ∈ [1, d1] and j ∈ [1 : n],
0 < 1
M
( Ŵ ′1X + b̂ ′ 11 T n ) ij < σ. (43)
Therefore, (
1 M ( Ŵ ′1X + b̂ ′ 11 T n ) ij + t ) ∈ (t, t+ σ). So,
Y (1) ([ Ŵ ′′i ]L i=1 , [ b̂′′i ]L i=1 ) =h ( Ỹ (1) ([ Ŵ ′′i ]L i=1 , [ b̂′′i ]L i=1 )) (∗) =hs−,s+ ( 1
M Ŵ ′1X +
1
M b̂′11 T n
) + h(t)1d11 T n
= 1
M Y (1)
([ Ŵ ′i ]L i=1 , [ b̂′i ]L i=1 ) + h(t)1d11 T n ,
where eq.(∗) is because for any x ∈ (t− σ, t+ σ), h(x) = h(t) + hs−,s+(x− t). (44)
Suppose the above argument holds for k (1 ≤ k ≤ L− 2). Then
Ỹ (k+1) ([ Ŵ ′′i ]L i=1 , [ b̂′′i ]L i=1 ) =Ŵ ′′k+1Y (k) ([ Ŵ ′′i ]L i=1 , [ b̂′′i ]L i=1 ) + b̂′′k+11 T n
=(−αk+1Ŵ ′k+1h(t)1dk+1
+ t1dk+1 + Πk+1i=1 αi M b̂′k+1)1 T n + αk+1Ŵ ′ k+1Y (k)
([ Ŵ ′′i ]L i=1 , [ b̂′′i ]L i=1 ) =αk+1Ŵ ′ k+1 ( h(t)1dk1 T n +
Πki=1αi M
Y (k) ([ Ŵ ′i ]L i=1 , [ b̂′i ]L i=1 )) + ( −αk+1Ŵ ′k+1h(t)1dk + t1dk+1 +
Πk+1i=1 αi M b̂′k+1
) 1Tn
= Πk+1i=1 αi M Ŵ ′k+1Y (k)
([ Ŵ ′i ]L i=1 , [ b̂′i ]L i=1 ) + Πk+1i=1 αi M b̂′k+11 T n + t1dk+11 T n
=t1dk+11 T n + Πk+1i=1 αi M
Ỹ (k+1) ([ Ŵ ′i ]L i=1 , [ b̂′i ]L i=1 ) .
Lemma 5 has proved that all components of Ỹ (k+1) ([ Ŵ ′i ]L i=1 , [ b̂′i ]L i=1 ) are contained in
Ỹ (1) ([ Ŵ ′i ]L i=1 , [ b̂′i ]L i=1 ) . Combining
t1d11 T n < t1d11 T n +
1
M Ỹ (1)
([ Ŵ ′i ]L i=1 , [ b̂′i ]L i=1 ) < (t+ σ)1d11 T n ,
we have
t1dk+11 T n < t1dk+11 T n + Πk+1i=1 αi M
Ỹ (k+1) ([ Ŵ ′i ]L i=1 , [ b̂′i ]L i=1 ) (∗) < (t+ σ)1dk+11 T n .
Here < are all element-wise, and inequality (∗) comes from the property of αi (eq. (41)). Furthermore, the (k + 1)-th layer output after the activation is Y (k+1) ([ Ŵ ′′i ]L i=1 , [ b̂′′i ]L i=1 ) =h ( Ỹ (k+1) ([ Ŵ ′′i ]L i=1 , [ b̂′′i ]L i=1
)) =h ( t1dk+11 T n + 1
M Ỹ (k+1)
([ Ŵ ′i ]L i=1 , [ b̂′i ]L i=1 )) (∗) =h(t)1dk+11 T n + hs−,s+ ( Πk+1i=1 αi M Ỹ (k+1) ([ Ŵ ′i ]L i=1 , [ b̂′i ]L i=1 ))
=h(t)1dk+11 T n + Πk+1i=1 αi M hs−,s+
( Ỹ (k+1) ([ Ŵ ′i ]L i=1 , [ b̂′i ]L i=1 )) =h(t)1dk+11 T n +
Πk+1i=1 αi M
Y (k+1) ([ Ŵ ′i ]L i=1 , [ b̂′i ]L i=1 ) ,
where eq. (∗) is because of eq. (44). The above argument is proved for any index k ∈ {1, . . . , L−1}.
Therefore, the output of the network is Y (L) ([ Ŵ ′′i ]L i=1 , [ b̂′′i ]L i=1 ) =Ŵ ′′LY (L−1) ([ Ŵ ′′i ]L i=1 , [ b̂′′i ]L i=1 ) + b̂′′L1 T n
= M
ΠL−1i=1 αi Ŵ ′L
( h(t)1dL−11 T n + ΠL−1i=1 αi M Y (L−1) ([ Ŵ ′i ]L i=1 , [ b̂′i ]L i=1 ))
+ ( − M
ΠL−1i=1 αi Ŵ ′Lh(t)1dL−1 + b̂ ′ L
) 1Tn
=Ŵ ′LY (L−1) ([ Ŵ ′i ]L i=1 , [ b̂′i ]L i=1 ) + b̂′L1 T n
=Y (L) ([ Ŵ ′i ]L i=1 , [ b̂′i ]L i=1 ) .
Therefore,
R̂ ([ Ŵ ′′i ]L i=1 , [ b̂′′i ]L i=1 ) = R̂ ([ Ŵ ′i ]L i=1 , [ b̂′i ]L i=1 ) = f(W̃ ).
We then introduce some small disturbances {
[δ′′Wi] L i=1 , [δ ′′ bi] L i=1
} into {[ Ŵ ′′i ]L i=1 , [ b̂′′i ]L i=1 } in
order to check the local optimality.
Since all comonents of Y (i) are in interval (t, t+σ), the activations in every hidden layers is realized at linear parts. Therefore, the output of network is
Ŷ ([ Ŵ ′′i + δ ′′ Wi ]L i=1 , [ b̂′′i + δ ′′ bi ]L i=1 ) = ( Ŵ ′′L + δ ′′ WL ) h ( · · ·h (( Ŵ ′′1 + δ ′′ W1 ) X + ( b̂′′1 + δ ′′ b1 ) 1Tn ) · · · ) + ( b̂′′L + δ ′′ bL ) 1Tn
= ( Ŵ ′′L + δ ′′ WL ) s+ ( · · · s+ (( Ŵ ′′1 + δ ′′ W1 ) X + ( b̂′′1 + δ ′′ b1 ) 1Tn ) + f(t)1d11 T n · · · ) + f(t)1dL1 T n + ( b̂′′L + δ ′′ bL ) 1Tn
=M1X +M21 T n
= [M1 M2] [ X 1Tn ] .
Similar to Lemma 5, [M1 M2] approaches W̃ as disturbances { [δWi] L i=1 , [δbi] L i=1 } approach 0
(element-wise). Combining that W̃ is a local minimizer of f(W ), we have R̂ ([ Ŵ ′′i + δ ′′ Wi ]L i=1 , [ b̂′′i + δ ′′ bi ]L i=1 ) = f ([M1 M2]) ≥ f(W̃ ) = R̂ ([ Ŵ ′′i ]L i=1 , [ b̂′′i ]L i=1 ) .
The proof is completed.
Step (b). Prove the constructed local minima are spurious.
Proof of Theorem 1. Without loss of generality, we assume that all activations are the same.
Let t be a non-differentiable point of the piece-wise linear activation function h with s− = lim
θ→0− h′(θ),
s+ = lim θ→0+
h′(θ).
Let σ be a constant such that h is linear in interval (t− σ, t) and interval (t, t+ σ). Then construct that
W̃ ′′1 = 1
M W̃ ′1, b̃ ′′ 1 =
1
M b̃′1 + t1d1 ,
W̃ ′′2 = 1
M̃ W̃ ′2, b̃ ′′ 2 = t1d2 −
1
M̃ h(t)W̃ ′21d2 +
1
MM̃ b̃′2,
W̃ ′′i = W̃ ′ i , b̃ ′′ i = −W̃ ′ih(t)1di−1 + t1di +
1
MM̃ b̃′i, (i = 3, 4, ..., L− 1)
and W̃ ′′L = MM̃W̃ ′ L, b̃ ′′ L = b̃ ′ L −MM̃W̃ ′Lh(t)1L−1,
where {[ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 } are constructed in Theorem 5, M is a large enough positive real such that 1
M ∥∥∥W̃ ′1X + b̃′11Tn∥∥∥ F < σ, (45)
and M̃ a large enough positive real such that
1
M̃
∥∥∥∥ 1M Ỹ (2) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 )∥∥∥∥ F < σ. (46)
Then, we prove by induction that for any i ∈ [2 : L − 1], all components of Ỹ (i) ([ W̃ ′′i ]L i=1 , [ b̃′′i ]L i=1 ) are in interval (t, t+ δ), and
Y (i) ([ W̃ ′′i ]L i=1 , [ b̃′′i ]L i=1 ) = h(t)1di1 T n + 1 M̃M Y (i) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) .
First,
Ỹ (1) ([ W̃ ′′i ]L i=1 , [ b̃′′i ]L i=1 ) = W̃ ′′1 X + b̃ ′′ 11 T n = 1 M (W̃ ′1X + b̃ ′ 11 T n ) + t1 T d11 T n . (47)
For any i ∈ [1 : d1] and j ∈ [1 : n], eq. (45) implies∣∣∣∣∣ ( 1 M (W̃ ′1X + b̃ ′ 11 T n ) ) ij ∣∣∣∣∣ ≤ 1M ∥∥∥W̃ ′1X + b̃′11Tn∥∥∥F < σ. Thus, (
1
M (W̃ ′1X + b̃ ′ 11 T n ) + t1 T d11 T n ) ij ∈ (t− σ, t+ σ). (48)
Therefore, the output of the first layer after the activation is Y (1) ([ W̃ ′′i ]L i=1 , [ b̃′′i ]L i=1 ) = h ( Ỹ (1) ([ W̃ ′′i ]L i=1 , [ b̃′′i ]L i=1 )) = h ( 1
M (W̃ ′1X + b̃ ′ 11 T n ) + t1d11 T n ) (∗) = h(t)1d11 T n + hs−,s+ ( 1
M
( W̃ ′1X + b̃ ′ 1 )) = h(t)1d11 T n + 1
M hs−,s+
(( W̃ ′1X + b̃ ′ 1 )) = h(t)1d11 T n + 1
M Y (1)
([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) ,
where eq. (∗) is from eq. (44) for any x ∈ (t− δ, t+ δ). Also,
Ỹ (2) ([ W̃ ′′i ]L i=1 , [ b̃′′i ]L i=1 ) =W̃ ′′2 Y (1) ([ W̃ ′′i ]L i=1 , [ b̃′′i ]L i=1 ) + b̃′′21 T n
= 1
M̃
( W̃ ′2 )( h(t)1d11 T n + 1
M Y (1)
([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 )) + t1d21 T n − 1
M̃ h(t)W̃ ′21d11 T n +
1
MM̃ b̃′21 T n
= 1
M̃M W̃ ′2Y (1)
([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) + 1 MM̃ b̃′21 T n + t1d21 T n
= 1
MM̃ Ỹ (2)
([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) + t1d21 T n .
Recall in Theorem 5 we prove all components of Ỹ (2) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) are positive. Combin-
ing the definition of M̃ (eq. (46)), we have
t1d21 T n <Ỹ (2) ([ W̃ ′′i ]L i=1 , [ b̃′′i ]L i=1 ) = 1
M̃M Ỹ (2)
([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) + t1d21 T n
<(t+ σ)1d21 T n .
Therefore, Y (2) ([ W̃ ′′i ]L i=1 , [ b̃′′i ]L i=1 ) =h ( Ỹ (2) ([ W̃ ′′i ]L i=1 , [ b̃′′i ]L i=1 )) =h ( 1
M̃M Y (2)
([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) + t1d21 T n ) =h(t)1d21 T n + hs−,s+ ( 1
M̃M Ỹ (2)
([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 )) =h(t)1d21 T n + 1
M̃M hs−,s+
( Ỹ (2) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 )) =h(t)1d21 T n + 1
M̃M Y (2)
([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) .
Suppose the above argument holds for k-th layer.
The output of (k + 1)-th layer before the activation is Ỹ (k+1) ([ W̃ ′′i ]L i=1 , [ b̃′′i ]L i=1 ) =W̃ ′′k+1Y (k) ([ W̃ ′′i ]L i=1 , [ b̃′′i ]L i=1 ) + b̃′′k+11 T n
=W̃ ′k+1 ( h(t)1dk1 T n + 1
M̃M Y (k)
([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 )) + ( −W̃ ′k+1h(t)1dk + t1dk+1 + 1
MM̃ b̃′k+1
) 1Tn
= 1
MM̃
( W̃ ′k+1Y (k) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) + b̃′k+11 T n ) + t1dk+11 T n
= 1
MM̃ Ỹ (k+1)
([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) + t1dk+11 T n .
Recall proved in Theorem 5 that all components of Ỹ (k+1) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) except those that
are 0 are contained in Ỹ (k) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) . We have
t1dk+11Tn < 1
MM̃ Ỹ (k+1)
([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) + t1dk+11 T n < (t+ σ)1dk+11Tn .
Therefore, Y (k+1) ([ W̃ ′′i ]L i=1 , [ b̃′′i ]L i=1 ) = h ( Ỹ (k) ([ W̃ ′′i ]L i=1 , [ b̃′′i ]L i=1 )) = h ( 1
MM̃ Ỹ (k+1)
([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) + t1dk+11 T n ) = h(t)1dk+11 T n + 1
MM̃ Y (k+1)
([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) .
Thus, the argument holds for any k ∈ {2, . . . , L− 1}. So,
Y (L) ([ W̃ ′′i ]L i=1 , [ b̃′′i ]L i=1 ) =W̃ ′′LY (L−1) ([ W̃ ′′i ]L i=1 , [ b̃′′i ]L i=1 ) + b̃′′L
=MM̃W̃ ′L ( h(t)1dL−11 T n + 1
MM̃ Y (L−1)
([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 )) + b̃′L1 T n −MM̃W̃ ′Lh(t)1dL−11Tn
=Y (L) ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) .
Therefore,
R̂ ([ W̃ ′′i ]L i=1 , [ b̃′′i ]L i=1 ) = R̂ ([ W̃ ′i ]L i=1 , [ b̃′i ]L i=1 ) . (49)
From eq. (49) and Theorem 5, we have R̂ ([ W̃ ′′i ]L i=1 , [ b̃′′i ]L i=1 ) < f ( W̃ ) ,
which completes the proof of local minimizer.
Furthermore, the parameter M used in Lemma 6 (not those in this proof) is arbitrary in a continuous interval (cf. eq. (40)), we have actually constructed infinite spurious local minima.
Theorem 1 relies on Assumption 4. We can further remove it by replacing Assumption 3 by a mildly more restrictive variant Assumption 5.
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 of Theorem 4 in Stage 1 of Theorem 1’s proof. We only need to prove the corollary under the assumption that s− + s+ = 0.
Let the local minimizer constructed in Lemma 4 be {[ Ŵi ]2 i=1 , [ b̂i ]2 i=1 } . Then, we construct a point in the parameter space whose empirical risk is smaller as follows:
W̃1 =  W̃1,[1:dX ] − αβT W̃1,[1:dX ] −W̃1,[1:dX ] + αβT W̃2,[1:dX ]
... W̃dY ,[1:dX ]
0(d1−dY −2)×dX
 ,
b̃1 =  W̃1,[dX+1] − η1 + γ W̃1,[dX+1] − η −W̃1,[dX+1] + η1 + γ W̃2,[dX+1] − η2
... W̃dY ,[dX+1] − ηdY
0(d1−dY −2)×1
 ,
W̃2 =  1 2s+ 1 s+ − 12s+ 0 0 · · · 0 0 · · · 0 0 0 0 1s+ 0 · · · 0 0 · · · 0 0 0 0 0 1s+ · · · 0 0 · · · 0 ... ... ... ... ... . . . ... ... . . .
... 0 0 0 0 0 · · · 1s+ 0 · · · 0
 ,
and
b̃2 =  η η2 ...
ηdY
 ,
where α, β, and ηi are defined the same as those in Theorem 4, and η is defined by eq. (27).
Then, the output of the first layer is
Y (1) ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 ) =hs−,s+ ( W̃1X + b̃11 T n )
=hs−,s+   W̃1,·X − αβTX − η11Tn + γ1Tn W̃1,·X − η1Tn −W̃1,·X + αβTX + η11Tn + γ1Tn W̃2,·X − η21Tn
... W̃dY ,·X − ηdY 1Tn
0d1−dY −21 T n
  .
Further, the output of the whole network is
Ŷ ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 )
=W̃2hs−,s+   W̃1,·X − αβTX − η11Tn + γ1Tn W̃1,·X − η1Tn −W̃1,·X + αβTX + η11Tn + γ1Tn W̃2,·X − η21Tn
... W̃dY ,·X − ηdY 1Tn
0d1−dY −21 T n
  + b̃21 T n
=W̃2hs−,s+   W̃1,·X − αβTX − η11Tn + γ1Tn W̃1,·X − η1Tn −W̃1,·X + αβTX + η11Tn + γ1Tn W̃2,·X − η21Tn
... W̃dY ,·X − ηdY 1Tn
0d1−dY −21 T n
  +  η η2 ... ηdY 1Tn .
Therefore, if j ≤ l′, the (1, j)-th component of Ŷ ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 ) is
( W̃2 ) 1 Ỹ (1) ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 ) j
= 1
2s+
( s− ( Ỹ1,j − αβTxj − η1 + γ ) + 2s+ ( Ỹ1,j − η ) − s+ ( −Ỹ1j + αβTxj + η1 + γ )) + η
= 1
2s+
( −s+ ( Ỹ1,j − αβTxj − η1 + γ ) + 2s+ ( Ỹ1,j − η ) − s+ ( −Ỹ1j + αβTxj + η1 + γ )) + η
= 1
2s+
( 2s+Ỹ1,j − 2s+η − 2s+γ ) + η
=Ỹ1,j − γ.
Otherwise (j > l′), the (1, j)-th component of Ŷ ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 ) is
( W̃2 ) 1 Ỹ (1) ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 ) j
= 1
2s+
( s+ ( Ỹ1,j − αβTxj − η1 + γ ) + 2s+ ( Ỹ1,j − η ) − s− ( −Ỹ1j + αβTxj + η1 + γ )) + η
= 1
2s+
( s+ ( Ỹ1,j − αβTxj − η1 + γ ) + 2s+ ( Ỹ1,j − η ) + s+ ( −Ỹ1j + αβTxj + η1 + γ )) + η
= 1
2s+
( 2s+Ỹ1,j − 2s+η + 2s+γ ) + η
=Ỹ1,j + γ, and the (i, j)-th (i > 1) component of Ŷ ([ W̃i ]2 i=1 , [ b̃i ]2 i=1 ) is Ỹi,j .
Therefore, we have( W̃2 ( W̃1xi + b̃1 ) + b̃2 − W̃ [ xi 1 ]) j =  − γ, j = 1, i ≤ l; γ, j = 1, i > l;
0, j ≥ 2.
Then, similar to Theorem 4, we have R̂ ([ W̃i ]L i=1 , [ b̃i ]L i=1 ) − R̂ ([ Ŵi ]L i=1 , [ b̂i ]L i=1 ) = 1
n n∑ i=1 l ( Yi, W̃2 ( W̃1xi + b̃1 ) + b̃2 ) − 1 n n∑ i=1 l ( Yi, Ŵ [ xi 1 ])
= 1
n n∑ i=1 ∇Ŷi l ( Yi, W̃ [ xi 1 ])( W̃2 ( W̃1xi + b̃11 T n ) + b̃21 T n − W̃ [ xi 1 ])
+ n∑ i=1 o (∥∥∥∥W̃2 (W̃1xi + b̃11Tn)+ b̃21Tn − W̃ [xi1 ]∥∥∥∥)
=− 2 n l′∑ i=1 V1,iγ + o(γ),
where V and l′ are also defined the same as those in Theorem 4. When γ is sufficiently small and sgn(γ) = sgn (∑l′
i=1 V1,i
) , we have that
R̂ (([
W̃i ]2 i=1 , [ b̃i ]2 i=1 )) < f(W̃ ).
This complete the proof of Corollary 3.

heading: A.5 A PREPARATION LEMMA
text: We now prove the preparation lemma used above.
Lemma 7. Suppose u = (u1 · · ·un) ∈ R1×n which satisfies u 6= 0 and n∑ i=1 ui = 0, (50)
while {x1,...,xn} is a set of vector ⊂ Rm×1. Suppose index set S = {1, 2, · · · , n}. Then for any series of real number {v1, · · · , vn}, there exists a non-empty separation I , J of S, which satisfies I ∪ J = S, I ∩ J = ∅ and both I and J are not empty, a vector β ∈ Rm×1,such that, (1.1) for any sufficiently small positive real α, i ∈ I , and j ∈ J , we have vi−αβTxi < vj−αβTxj; (1.2) ∑ i∈I ui 6= 0.
Proof. If there exists a non-empty separation I and J of the index set S, such that when β = 0, (1.1) and (1.2) hold, the lemma is apparently correct.
Otherwise, suppose that there is no non-empty separation I and J of the index set S such that (1.1) and (1.2) hold simultaneously when β = 0.
Some number vi in the sequence (v1, v2, · · · , vn) are probably equal to each other. We rerarrange the sequence by the increasing order as follows,
v1 = v2 = · · · = vs1 < vs1+1 = · · · = vs2 < · · · < vsk−1+1 = · · · = vsk = vn, (51)
where sk = n.
Then, for any j ∈ {1, 2, · · · , k − 1}, we argue that sj∑ i=1 ui = 0.
Otherwise, suppose there exists a sj , such that sj∑ i=1 ui 6= 0.
Let I = {1, 2, ..., sj} and J = {sj + 1, ..., n}. Then, when β = 0, we have
vi − αβTxi = vi < vj = vj − αβTxj ,
and ∑ i∈I ui = sj∑ i=1 ui 6= 0,
which are exactly the arguments (1.1) and (1.2). Thereby we construct a contrary example. Therefore, for any j ∈ {1, 2, · · · , k − 1}, we have
sj∑ i=1 ui = 0.
Since we assume that u 6= 0, there exists an index t ∈ {1, . . . , k−1}, such that there exists an index i ∈ {st + 1, ..., st+1} that ui 6= 0. Let l ∈ {st + 1, ..., st+1} is the index such that xl has the largest norm while ul 6= 0:
l = arg max j∈{st+1,...,st+1}, uj 6=0
‖xj‖ . (52)
We further rearrange the sequence (vst+1, ..., vst+1) such that there is an index l ′ ∈ {st + 1, . . . , st+1}, ‖xl′‖ = max
j∈{st+1,...,st+1}, uj 6=0 ‖xj‖ ,
and
∀i ∈ {st + 1, ..., l′}, 〈xl′ , xi〉 ≥ ‖xl′‖2 ; (53) ∀i ∈ {l′ + 1, · · · , st+1}, 〈xl′ , xi〉 < ‖xl′‖2 . (54)
It is worth noting that it is probably l′ = st+1, but it is a trivial case that would not influence the result of this lemma.
Let I = {1, ..., l′}, J = {l′ + 1, ..., n}, and β = xl′ . We prove (1.1) and (1.2) as follows. Proof of argument (1.1).
We argue that for any i ∈ I , vi − αβTxi ≤ vl′ − αβTxl′ and for any j ∈ J , vj − αβTxj > vl′ − αβTxl′ . There are three situations:
(A) i ∈ {1, . . . , st} and j ∈ {st+1 + 1, · · · , n}. Applying eq. (51), for any i ∈ {1, . . . , st} and j ∈ {st+1 + 1, · · · , n}, we have that vi < vl′ and vj > vl′ . Therefore, when α is sufficiently small, we have the following inequalities,
vi − αβTxi < vl′ − αβTxl′ , vj − αβTxj > vl′ − αβTxl′ .
(B) i ∈ {st + 1, · · · , l′}. Applying eq. (53) and because of α > 0, we have
−α〈β, xi〉 ≤ −α ‖β‖2 = −α〈β, xl′〉.
Since vi = vl′ , it further leads to
vi − αβTxi ≤ vl′ − αβTxl′ .
(C) j ∈ {l′ + 1, · · · , st+1}. Similarly, applying eq. (54) and because of α > 0, we have
−α〈β, xj〉 > −α ‖β‖2 = −α〈β, xl′〉.
Since vj = vl′ , it further leads to
vj − αβTxj > vl′ − αβTxl′ ,
which is exactly the argument (1.1).

heading: Proof of argument (1.2).
text: We argue that for any i ∈ {st + 1, · · · , l′ − 1}, ui = 0. Otherwise, suppose there exists an i ∈ {st + 1, · · · , l′ − 1} such that ui 6= 0. From eq. (52), we have ‖xi‖ ≤ ‖xl′‖. Therefore,
〈xl′ , xi〉 ≤ ‖xl′‖‖xi‖ ≤ ‖xl′‖2,
where the first inequality strictly holds if the vector xl′ and xi have the same direction, while the second inequlity strictly holds when xi and xl′ have the same norm. Because xl′ 6= xi, we have the following inequality, 〈xl′ , xi〉 < ‖xl′‖2, which contradicts to eq. (53), i.e.,
〈xl′ , xi〉 ≥ ‖xl′‖2, ∀i ∈ {st + 1, · · · , l′}.
Therefore, ∑ i∈I ui = st∑ i=1 ui + l′−1∑ i=st+1 ui + ul′ = ul′ 6= 0,
which is exactly the argument (1.2).
The proof is completed.
Remark. For any i ∈ {l′ + 1, ..., st+1}, we have( vi − αβTxi ) − ( vl′ − αβTxl′ ) = αβT (xl′ − xi), (55)
while for any j ∈ {st+1 + 1, ..., n}, we have( vj − αβTxj ) − ( vl′ − αβTxl′ ) = vj − vl′ + αβT (xl′ − xj). (56)
Because vj > vl′ , when the real number α is sufficiently small, we have
αβT (xl′ − xi) < vj − vl′ + αβT (xl′ − xj).
Applying eqs. (55) and (56), we have( vi − αβTxi ) − ( vl′ − αβTxl′ ) < ( vj − αβTxj ) − ( vl′ − αβTxl′ ) .
Therefore, if l′ < st+1, we have
min i∈{l′+1,...,n}
( vi − αβTxi ) − ( vl′ − αβTxl′ ) = min i∈{l′+1,...,st+1} αβT (xl′ − xi); (57)
while if l′ = st+1,
min i∈{l′+1,...,n}
( vi − αβTxi ) − ( vl′ − αβTxl′ ) = min i∈{l′+1,...,n} vi − vl + αβT (xl′ − xi). (58)
Eqs. (57) and (58) make senses because l′ < n. Otherwise, from Lemma 7 we have ∑n i=1 ui 6= 0, which contradicts to the assumption.

heading: B PROOFS OF THEOREM 2, THEOREM 3, COROLLARY 1, AND COROLLARY 2
text: This appendix gives the proofs of Theorem 2, Theorem 3, Corollary 1, and Corollary 2 omitted from Section 4.

heading: B.1 SQUARED LOSS
text: 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 to the prediction Ŷ .
Proof. The second derivative of the empirical risk R̂ under squared loss with respect to the prediction Ŷ is
∂2lce(Y, Ŷ ) ∂Ŷ 2 = ∂2(y − Ŷ )2 ∂Ŷ 2 = 2 > 0.
Therefore, the empirical risk R̂ under squared loss is strictly convex with respect to prediction Ŷ .

heading: B.2 SMOOTH AND MULTILINEAR PARTITION.
text: If the activations are all linear functions, the neural networks is reduced to a 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 a smooth and multilinear region in the loss surface. When some parameter changes by a 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 is 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 in activations correspond to the non-differentiable boundaries between cells on the loss surface.

heading: B.3 EVERY LOCAL MINIMUM IS GLOBALLY MINIMAL WITHIN A CELL.
text: Proof of Theorem 2. In every cell, the input sample points flows through the same linear parts of the activations no matter what values the parameters are.
(1) We first proves that the empirical risk R̂ equals to a convex function with respect to a variable Ŵ that is calculated from the parameters W .
Suppose (W1,W2) is a local minimum within a cell. We argue that n∑ i=1 l (yi,W2diag (A·,i)W1xi) = n∑ i=1 l ( yi, A T ·,idiag(W2)W1xi ) , (59)
where A·,i is the i-th column of the following matrix
A =  h ′ s−,s+((W1)1,·x1) · · · h ′ s−,s+((W1)1,·xn) ... . . .
... h′s−,s+((W1)d1,·x1) · · · h ′ s−,s+((W1)d1,·xn)  . (60) The left-hand side (LHS) is as follows,
LHS = n∑ i=1 l (yi,W2diag (A·,i)W1xi)
= n∑ i=1 l (yi, [(W2)1,1A1,i · · · (W2)1,d1Ad1,i]W1xi) .
Meanwhile, the right-hand side (RHS) is as follows,
RHS = n∑ i=1 l ( yi, A T ·,idiag(W2)W1xi ) ,
= n∑ i=1 l (yi, [(W2)1,1A1,i · · · (W2)1,d1Ad1,i]W1xi) .
Apparently, LHS = RHS. Thereby, we proved eq. (59).
Afterwards, we define Ŵ1 = diag(W2)W1, (61)
and then straighten the matrix Ŵ1 to a vector Ŵ , Ŵ = ( (Ŵ1)1,· · · · (Ŵ1)d1,· ) , (62)
Also define X̂ = (A·,1 ⊗ x1 · · · A·,n ⊗ xn) . (63)
Then, we can prove that the following equations,( AT·,1Ŵ1x1 · · · AT·,nŴ1xn ) = ( (Ŵ1)1,· · · · (Ŵ1)d1,· ) (A·,1 ⊗ x1 · · · A·,n ⊗ xn)
=Ŵ X̂. (64)
Applying eq. (64), the empirical risk is transferred to a convex function as follows,
R̂(W1,W2) = 1
n n∑ i=1 l ( yi, (A·,i) T diag(W2)W1xi ) = 1 n n∑ i=1 l ( yi, (A·,i) T Ŵ1xi ) = 1
n n∑ i=1 l ( yi, Ŵ X̂i ) . (65)
We can see that the empirical risk is rearranged as a convex function in terms of Ŵ which unite the two weight matrices W1 and W2 and the activation h are together as Ŵ .
Applying eqs. (61) and (62), we have
Ŵ = [(W2)1(W1)1,· · · · (W2)d1(W1)d1,·] .
(2) We then prove that the local minima (including global minima) of the empirical risk R̂ with respect to the parameter W is also local minima with respect to the corresponding variable Ŵ .
We first prove that for any i ∈ [1 : d1d2], we have
eiX̂∇ = 0,
where∇ is defined as follows,
∇ = [ ∇(Ŵ X̂)
1
l ( Y1, ( Ŵ X̂ ) 1 ) · · · ∇(Ŵ X̂) n l ( Yn, ( Ŵ X̂ ) n )]T .
To see this, we divide i into two cases: (W2)i 6= 0 and (W2)i = 0. Case 1: (W2)i 6= 0.
The local minimizer of the empirical risk R̂ with respect to the parameter W satisfies the following equation,
∂R̂ ∂(W1)i,j = 0.
Therefore,
0 = ∂R̂
∂(W1)i,j
=
∂ ( n∑ k=1 l ( Y·,k, ( Ŵ X̂ ) ·,k )) ∂(W1)i,j
= n∑ k=1 [ 0 · · · 0 (W2)i 0 · · · 0 ] X̂k∇(Ŵ X̂)·,k l ( Y·,k, ( Ŵ X̂ ) ·,k ) ,︸ ︷︷ ︸
dX(i−1)+j−1 ︸ ︷︷ ︸ dXd1−dX(i−1)−j
(66)
where (W2) is a vector and (W2)i is its i-th component.
Then, divid the both hand sides of eq. (66) with (W2)i, we can get the following equation,
(edX(i−1)+jX̂)∇ = 0.
Case 2: (W2)i = 0. Suppose u1 ∈ Rd0 is a unitary vector, u2 ∈ R is a real number, and ε is a small enough positive constant. Then, define a disturbance of W1 and W2 as follows,
∆W1 = [ 0 · · · 0 εu1 0 · · · 0 ] ,︸ ︷︷ ︸ dX(i−1) ︸ ︷︷ ︸ d1dX−dX i
∆W2 = [ 0 · · · 0 ε2u2 0 · · · 0 ] .︸ ︷︷ ︸
i−1 ︸ ︷︷ ︸ d1−i
When ε is sufficiently small, ∆W1 and ∆W2 are also sufficiently small. Since (W1,W2) is a local minimum, we have
1
n n∑ k=1 l ( Yk, (( Ŵ + ∆ ) X̂ ) k ) =R̂(W1 + ∆W1,W2 + ∆W2) ≥R̂(W1,W2)
= 1
n n∑ k=1 l ( Yk, ( Ŵ X̂ ) k ) , (67)
where ∆ is defined as follows,
∆ = [(W2 + ∆W2)1(W1 + ∆W1)1 · · · (W2 + ∆W2)d1(W1 + ∆W1)d1 ] − [(W2)1(W1)1 · · · (W2)d1(W1)d1 ]
(∗) = [ 0 · · · 0 ε2u2 (εu1 + (W1)i) 0 · · · 0 ] .︸ ︷︷ ︸
dX(i−1) ︸ ︷︷ ︸ d1dX−dX i
(68)
Here, eq. (∗) comes from (W2)i = 0. Rearrange eq. (67) and apply the Taylor’s Theorem, we can get that
∆ · X̂∇+ O ( ‖∆ · X̂‖2 ) ≥ 0.
Applying eq. (68), we have[ 0 · · · 0 ε2u2 (εu1 + (W1)i) 0 · · · 0 ] X̂∇︸ ︷︷ ︸
dX(i−1) ︸ ︷︷ ︸ dXd1−idX
+ε4O ( ‖ [ 0 · · · 0 u2 (εu1 + (W1)i) 0 · · · 0 ] X̂‖2 ) ︸ ︷︷ ︸ dX(i−1) ︸ ︷︷ ︸ dXd1−idX
(∗∗) = [ 0 · · · 0 ε3u2u1 0 · · · 0 ] X̂∇︸ ︷︷ ︸
dX(i−1) ︸ ︷︷ ︸ dXd1−idX
+ε4O ( ‖ [ 0 · · · 0 u2 (εu1 + (W1)i) 0 · · · 0 ] X̂‖2 ) ︸ ︷︷ ︸ dX(i−1) ︸ ︷︷ ︸ dXd1−idX
= ε3 [ 0 · · · 0 u2u1 0 · · · 0 ] X̂∇+ o(ε3)︸ ︷︷ ︸ dX(i−1) ︸ ︷︷ ︸ dXd1−idX
(69)
≥ 0 . (70)
Here, eq. (∗∗) can be obtained from follows. Because W2 is a local minimizer, for any component (W2)i of W2,
∂ (∑n k=1 l ( Yk, ( Ŵ X̂ ) k )) ∂(W2)i =0,
which leads to
[ 0 · · · 0 (W1)i 0 · · · 0 ] X̂∇ = 0.︸ ︷︷ ︸ dX(i−1) ︸ ︷︷ ︸ dXd1−idX
When ε approaches 0, eq. (69) leads to the following inequality,
[ 0 · · · 0 u2u1 0 · · · 0 ] X̂∇ ≥ 0.︸ ︷︷ ︸ dX(i−1) ︸ ︷︷ ︸ dXd1−idX
Since u1 and u2 are arbitrarily picked (while the norms equal 1), the inequality above further leads to
[ 0 · · · 0 ej 0 · · · 0 ] X̂∇ = 0,︸ ︷︷ ︸ dX(i−1) ︸ ︷︷ ︸ dXd1−idX
(71)
which finishes the proof of the argument.
Therefore, for any i and j, we have proven that
ed0(i−1)+jX̂∇ = 0,
which demonstrates that X̂∇ = 0,
which means Ŵ is also a local minimizer of the empirical risk R̂,
R̂(W ) = n∑ i=1 l(Yi,WX̂i). (72)
(3) Applying the property of convex function, Ŵ is a global minimizer of the empirical risk R̂, which leads to (W1,W2) is a global minimum inside this cell.
The proof is completed.

heading: B.4 EQUIVALENCE CLASSES OF LOCAL MINIMUM VALLEYS IN CELLS.
text: Proof of Theorem 3 and Corollary 1. In the proof of Theorem 2, we constructed a map Q: (W1,W2) → Ŵ . Further, in any fixed cell, the represented hypothesis of a neural network is uniquely determined by Ŵ .
We first prove that all local minima in a cell are concentrated as a local minimum valley.
Since the loss function l is strictly convex, the empirical risk has one unique local minimum (which is also a 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 a cell, when W1 expands by a positive real factor α to W ′1 and W2 shrinks by the same positive real factor α to W ′2, we have Q(W1,W2) = Q(W ′ 1,W ′ 2), i.e., the Ŵ remains invariant.
Further, we argue that all local minima in a cell are connected with each other by a continuous path, on which the empirical risk is invariant. For every local minima pair (W1,W2) and (W ′1,W ′ 2), we have diag(W2)W1 = diag(W ′2)W ′ 1. (73) Since h′s−,s+(W1X) = h ′ s−,s+(W ′ 1X) (element-wise), for every i ∈ [1, d1],
sgn ((W2)i) = sgn ((W ′ 2)i) .
Therefore, a continuous path from (W1,W2) to (W ′1,W ′ 2) can be constructed by finite moves, each of which expands a component of W2 by a real constant α and then shrinks the corresponding line of W1 by the same constant α.
We then prove that all local minima in a cell constitute an equivalence class.
Define an operation ∼R as follows,
(W 11 ,W 1 2 ) ∼R (W 21 ,W 22 ),
if Q(W 11 ,W 1 2 ) = Q(W 2 1 ,W 2 2 ).
We then argue that ∼R is an equivalence relation. The three properties of equivalence relations are checked as follows.
(1) Reflexivity:
For any (W1,W2), we have Q(W1,W2) = Q(W1,W2).
Therefore, (W1,W2) ∼R (W1,W2).
(2) Symmetry:
For any pair (W 11 ,W 1 2 ) and (W 2 1 ,W 2 2 ), Suppose that
(W 11 ,W 1 2 ) ∼R (W 21 ,W 22 ).
Thus, Q(W 11 ,W 1 2 ) = Q(W 2 1 ,W 2 2 ).
Apparently, Q(W 21 ,W 2 2 ) = Q(W 1 1 ,W 1 2 ).
Therefore, Q(W 21 ,W 2 2 ) ∼R Q(W 11 ,W 12 ).
(3) Transitivity:
For any (W 11 ,W 1 2 ), (W 2 1 ,W 2 2 ), and (W 3 1 ,W 3 2 ), suppose that
(W 11 ,W 1 2 ) ∼R (W 21 ,W 22 ),
(W 21 ,W 2 2 ) ∼R (W 31 ,W 32 ).
Then,
Q(W 11 ,W 1 2 ) = Q(W 2 1 ,W 2 2 ),
Q(W 21 ,W 2 2 ) = Q(W 3 1 ,W 3 2 ).
Apparently, Q(W 11 ,W 1 2 ) = Q(W 2 1 ,W 2 2 ) = Q(W 3 1 ,W 3 2 ).
Therefore, (W 11 ,W 1 2 ) ∼R (W 31 ,W 32 ).
We then prove the mapping Q is the quotient map.
Define a map as follows,
T : (W1,W2)→ (diag(W2)W1,11×d1).
We then define an operator ⊕ as,
(W 11 ,W 1 2 )⊕ (W 21 ,W 22 ) = T (W 11 ,W 12 ) + T (W 21 ,W 22 ),
the inverse of (W1,W2) is defined to be (−W1,W2) and the zero element is defined to be (0,11×d1). Obviously, the following is a linear mapping:
Q : ((Rd1×dX ,R1×d1),⊕)→ (R1×dXd1 ,+).
For any pair (W 11 ,W 1 2 ) and (W 2 1 ,W 2 2 ), we have
(W 11 ,W 1 2 ) ∼R (W 21 ,W 22 ),
if and only if (W 11 ,W 1 2 )⊕ (−W 21 ,W 22 ) ∈ Ker(Q). Therefore, the quotient space (Rd1×dX ,R1×d1)/Ker(Q) is a definition of the equivalence relation ∼R. The proof is completed.

heading: B.5 LINEAR COLLAPSE.
text: When there is no nonlinearities in the activations, there is apparently no non-differentiable regions on the loss surface. In other words, the loss surface is a single smooth and multilinear cell.

Review summaries:
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. 

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.