Year: 2020

Abstract:
Network pruning, or sparse network has a long history and practical significance in modern applications. Although the loss functions of neural networks may yield bad landscape due to non-convexity, we focus on linear activation which already owes benign landscape. With no unrealistic assumption, we conclude the following statements for the squared loss objective of general sparse linear neural networks: 1) every local minimum is a global minimum for scalar output with any sparse structure, or non-intersected sparse first layer and dense other layers with orthogonal training data; 2) sparse linear networks have sub-optimal local-min for only sparse first layer due to low rank constraint, or output larger than three dimensions due to the global minimum of a sub-network. Overall, sparsity breaks the normal structure, cutting out the decreasing path in original fully-connected networks.

heading: 1 INTRODUCTION
text: Deep neural networks (DNNs) have achieved remarkable empirical successes in the domains of computer vision, speech recognition, and natural language processing, sparking great interests in the theory behind their architectures and training. However, DNNs are often found to be highly overparameterized, making them computationally expensive with large amounts of memory and computational power. For example, it may take up to weeks on a modern multi-GPU server for large datasets such as ImageNet (Deng et al., 2009). Hence, DNNs are often unsuitable for smaller devices like embedded electronics, and there is a pressing demand for techniques to optimize models with reduced model size, faster inference and lower power consumption.
Sparse networks, that is, neural networks in which a large subset of the model parameters are zero, have emerged as one of the leading approaches for reducing model parameter count. It has been shown empirically that deep neural networks can achieve state-of-the-art results under high levels of sparsity (Han et al., 2015b; Gale et al., 2019; Louizos et al., 2017a). Modern sparse networks are mainly obtained from network pruning (Zhu & Gupta, 2017; Lee et al., 2018; Liu et al., 2018; Frankle & Carbin, 2018), which has been the subject of a great deal of work in recent years. However, training a sparse network with fixed sparsity patterns is difficult (Evci et al., 2019) and few theoretical understanding of general sparse networks has been provided.
Previous work has already analyze deep neural networks, showing that the non-convexity of the associated loss functions may cause complicated and strange optimization landscapes. However, the property of general sparse networks is poorly understood. Saxe et al. (2013) empirically showed that the optimization of deep linear models exhibits similar properties as deep nonlinear models, and for theoretical development, it is natural to begin with linear models before studying nonlinear models (Baldi & Lu, 2012). In addition, several works (Sun et al., 2020) have show bad minimum exists with nonlinear activation. Hence, it is natural to begin with linear activation to understand the impact of sparsity.
In this article, we go further to consider the global landscape of general sparse linear neural networks. We need to emphasize that dense deep linear networks already satisfy that every local minimum is a global minimum under mild conditions (Kawaguchi, 2016; Lu & Kawaguchi, 2017), but findings are different and complicated for sparse linear network. The goal of this paper is to study the relation between sparsity and local minima with the following contributions:
• First, we point out that every local minimum is a global minimum in scalar target case with any depths, any widths and any sparse structure. Besides, we also briefly show that
similar results hold for non-overlapping filters and orthogonal data feature when sparsity only occurs in the first layer. • Second, we find out that sparse connections would already give sub-optimal local minima
in general non-scalar case through analytic and numerical examples built on convergence analyze. The local-min may be produced from two situations: a sub-sparse linear network which owes its minimum as a local-min of the original sparse network; a rank-deficient solution between different data features due to sparse connections, while both cases verify the fact that sparsity cuts out the decreasing path in original fully-connected networks.
Overall, we hope our work contributes to a better understanding of the landscape of sparsity network on simple neural networks, and provide insights for future research.
The remainder of our paper is organized as follows. In Section 2, we derive the positive findings of shallow sparse linear networks, providing similar landscape as dense linear networks. In Section 3, we give several examples to show the existence of bad local-min for non-scalar case. In section 4, we briefly generalize the results from shallow to deep sparse linear networks. Some proofs are in Appendix.

heading: 1.1 RELATED WORK
text: There is a rapidly increasing literature on analyzing the loss surface of neural network objectives, surveying all of which is well outside our scope. Thus, we only briefly survey the works most related to ours.
Local minima is Global. The landscape of a linear network date back to Baldi & Hornik (1989), proving that shallow linear neural networks do not suffer from bad local minima. Kawaguchi (2016) generalized same results to deep linear neural networks, and subsequent several works (Arora et al., 2018; Du & Hu, 2019; Eftekhari, 2020) give direct algorithm-type convergence based on this benign property, though algorithm analysis is beyond the scope of this paper. However, situations are quite complicated with nonlinear activations. Multiple works (Ge et al., 2017; Safran & Shamir, 2018; Yun et al., 2018) show that spurious local minima can happen even in two-layer network with population or empirical loss, some are specific to two-layer and difficult to generalize to general multilayer cases. Another line of works (Arora et al., 2018; Allen-Zhu et al., 2018; Du & Hu, 2019; Du et al., 2018; Li et al., 2018; Mei et al., 2018) understands the landscape of neural network in an overparameterized setting, discovering benign landscape with or without gradient method. Since modern sparse networks reserve few parameters compared to overparameterization, we still seek a fundamental view of sparsity in contrast. Our standpoint is that spurious local minima can happen when applied with specific sparsity even in linear networks.
Sparse networks. Sparse networks (Han et al., 2015b;a; Zhu & Gupta, 2017; Frankle & Carbin, 2018; Liu et al., 2018) have a long history, but appears heavily on the experiments, and mainly related to network pruning, which has practical importance for reducing model parameter count and deploying diverse devices. However, training sparse networks (from scratch) suffers great difficulty. Frankle & Carbin (2018) recommend reusing the sparsity pattern found through pruning and train a sparse network from the same initialization as the original training (‘lottery’) to obtain comparable performance and avoid bad solution. Besides, for fixed sparsity patterns, Evci et al. (2019) attempt to find a decreasing objective path from ‘bad’ solutions to the ‘good’ ones in the sparse subspace but fail, showing bad local minima can be produced by pruning, while we give more direct view of simple examples to verify this. Moreover, several recent works also give abundant methods (Molchanov et al., 2017; Louizos et al., 2017b; Lee et al., 2018; Carreira-Perpinán & Idelbayev, 2018) for choosing weights or sparse network structure while achieving similar performance. In theoretical view, Malach et al. (2020) prove that a sufficiently over-parameterized neural network with random weights contains a subnetwork with roughly the same accuracy as the target network, providing guarantee for ‘good’ sparse networks. Some works analyze convolutional network (Shalev-Shwartz et al., 2017; Du et al., 2018) as a specific sparse structure. Brutzkus & Globerson (2017) analyze non-overlapping and overlapping structure as we do, but with weight sharing to simulate CNN-type structure, and under teacher-student setting with population risk. We do not follow CNN-type network but in general sparse networks, though still linear, to conclude straightforward results.

heading: 2 LANDSCAPE OF SHALLOW SPARSE LINEAR NETWORKS

heading: 2.1 PRELIMINARIES AND NOTATION
text: We use bold-faced letters (e.g., w and a) to denote vectors, capital letters (e.g., W = [wij ] and A = [aij ]) for matrices. Let PX be the orthogonal projection to the column space of the matrix X , and λi(H) is the i-th smallest eigenvalue of a real symmetric matrix H .
We consider the training samples and their outputs as {(xi,yi)}ni=1 ⊂ Rdx × Rdy , which may come from unknown distribution D. We form the data matrices X = [x1, . . . ,xn]T ∈ Rn×dx and Y = [y1, . . . ,yn]
T ∈ Rn×dy , respectively. In our analysis in Sections 2 and 3, we consider a two-layer (sparse) linear neural network with squared loss:
min W,A
L(W,A) := 1
2 ‖Y −XWA‖2F , (1)
where the first layer weight matrix W = [w1, . . . ,wd] ∈ Rdx×d , and the second layer weight matrix A = [a1, . . . ,ad]T ∈ Rd×dy . After weights pruning or sparsity constraint, many weights parameters become zero and would not be updated during retraining. We adopt Sj := {k : wkj = 0} as pruned dimensions in the j-th column ofW , and−Sj := Scj = [dx]\Sj , where [d] := {1, . . . , d}. In addition, wj,S denotes the sub-vector of wj choosing the positions in S, XS the sub-matrix of X choosing the column indices in S. We let pj = dx − |Sj |, where |S| is the cardinality of the set S. Then wj,−Sj ∈ Rpj is the remaining j-th column in first layer weight which leaves out pruned dimension set Sj . Similarly, X−Sj ∈ Rn×pj means the remaining data matrix connected to j-th node in the first layer.
Finally, for simplicity, we denote X−j = X−Sj , w−j = wj,−Sj , and (̃·) as the pruned layer weight with several zero elements not updated all along, if no ambiguity.
Before we begin, a small note on the sparse structure we concern: there may have unnecessary connections and nodes, such as a node with zero out-degree which can be retrieved and excluded from the final layer to the first layer, and other cases are showing in Appendix C. Thus we do not consider them in the subsequent proof and assume each data dimension has valid output connection, i.e., ∩dj=1Sj = ∅.

heading: 2.2 SCALAR CASE
text: In the scalar case, assume dy = 1. We then simplify A = (a1, . . . , ad) T . When pruning any weight ai in the second layer, the output of the i-th node in the first layer contribute zero to final output. Hence wi can also be pruned. Without loss of generality, we assume second layer parameters are not pruned. After pruning several parameters, the original problem becomes
min w−i,ai
L(W̃ ,A) := 1
2 ∥∥∥∥∥∥∥Y − (X−1, . . . , X−i, . . . , X−d) a1w−1... adw−d  ∥∥∥∥∥∥∥ 2
F
. (2)
Theorem 1 For a two-layer linear neural network with scalar output and any sparse structure, every local minimum is a global minimum.
Proof: From Eq. (2), if a local minimizer satisfies ai = 0 for some 1 ≤ i ≤ d, then based on the second order condition for a local minima, we have
 ∂2L ∂a2i
∂2L
∂ai∂wT−i ∂L
∂w−i∂ai
∂L
∂w−i∂wT−i
 0, (3)
which implies that wT−iX−iXT−iw−i −(Y −∑di=1X−iw−iai)T X−i −XT−i ( Y − ∑d i=1X−iw−iai ) 0  0. (4) Then XT−i ( Y − ∑d i=1X−iw−iai ) = 0, which is the global minimizer condition of w−iai.
Otherwise, ai 6= 0, then from the first-order condition for a local minima,
∂L
∂w−i = aiX
T −i
( Y −
d∑ i=1 X−iw−iai
) = 0,
showing that XT−i ( Y − ∑d i=1X−iw−iai ) = 0, which also gives the global minimizer condition of w−iai. Hence every local minimum is a global minimum.

heading: 2.3 NON-SCALAR CASE WITH DENSE SECOND LAYER
text: Now we discuss the case of non-scalar outputs. By the intractable and various sparse structure, we first consider pruning only the first layer while retaining the dense second layer. Then the remaining problem is formulated as follows:
min w−i,ai
L(W̃ ,A) := 1
2 ∥∥∥∥∥Y − d∑
i=1
X−iw−ia T i ∥∥∥∥∥ 2
F
. (5)
Intuitively, if we can separate the weight parameters into d parts, based on linear network results, we can still guarantee no bad local-min. We show that non-overlapping first layer weight or disjoint feature extractor, as the left graph of Figure 1 depicts, and orthogonal data feature meet requirements.
Theorem 2 For a two-layer sparse linear neural network with dense second layer, assume that X is full column rank, and ∀ i 6= j, XT−iX−j = 0. Then every local minimum is global.
Proof: Since ∀ i 6= j, XT−iX−j = 0 and X is full column rank, X−i and X−j share no same columns. Additionally, from our assumption ∩dj=1Sj = ∅, we have ∩dj=1Sj = [dx], meaning that (X−1, . . . , X−d) is X with different arrangement of columns. Hence,
Y = PXY + (I − PX)Y = X(XTX)−1XTY + (I − PX)Y = d∑
i=1
X−iZi + (I − PX)Y, (6)
where Zi = ( (XTX)−1XTY ) −Si
is the sub-matrix choosing the row indices in −Si. Then we only need to consider the objective:
min w−i,ai
L(W̃ ,A) = 1
2 ∥∥∥∥∥ d∑
i=1
X−i ( Zi −w−iaTi )∥∥∥∥∥ 2
F
= 1
2 d∑ i=1 ∥∥X−i (Zi −w−iaTi )∥∥2F . (7)
Hidden layer 1
Input layer
Output layer
Hidden layer 1 Hidden layer 2 Hidden layer 3 Input layer Output layer
We will see that the objective has already been separated into d parts, while each part is a two-layer dense linear network with full column rank data matrix. Based on Theorem 2.2 in Lu & Kawaguchi (2017) or Eckart-Young-Mirsky theorem (Eckart & Young, 1936; Mirsky, 1960), we obtain that every local minimum is a global minimum.
Additionally, we need to explain the assumption that non-overlapping filters in the first layer involves convolution networks (Brutzkus & Globerson, 2017) if weight sharing is used. Otherwise, we will show a bad local minima exists when the first layer is overlapped or training data is not orthogonal in Section 3.
2.4 GENERAL CASE WITH dy = 2
Previous findings imply positive results with one-dimension outputs, or specific sparse structure and data assumption. In this subsection, we discuss an arbitrary sparse structure with outputs of dimension dy = 2. We first prove that some connections still owe common benign landscape which can be removed.
Theorem 3 For a sparse two-layer network, a node with full out-degree and one in-degree can be removed if we consider the remaining structure with objective under some projected data, having no influence for spurious local minima.
Previous result simplifies the sparse structure including such a hidden node with one connection to input and full connection to output. Next, we will provide another type reduction with only one connection to output when sparsity is applied to both layers with dy = 2.
We mention the final layer output as Node 1 and Node 2, and the hidden nodes which have only one connection to the output layer as R1 and R2 while the remaining full connection set as R. Set T1 = ∩j∈R1Sj , T2 = ∩j∈R2Sj . We define U(T ) = {j : wij 6= 0, i ∈ T } as the hidden node set connected with data feature in T . When the hidden node sets connected to T1 and T2 satisfy the condition below, we are able to simply the sparse structure into the dense layer case.
Theorem 4 For a sparse two-layer linear network with dy = 2, if U(T1 ∩ T2) ∩ U(T1 \ T2) = ∅ and U(T1 ∩ T2) ∩ U(T2 \ T1) = ∅, then there is a sub-network with dense second layer optimized with some projected training data, sharing the same local minimum for the remaining parameters.
The formal proof of the theorem can be found in Appendix E. Additionally, from the proof of Theorem 4, the objective is converted into two objectives with weight sharing in the first layer even the assumption does not meet. Weight sharing structure has been shown in some related work (Shalev-Shwartz et al., 2017; Brutzkus & Globerson, 2017), so we do not give detailed description and leave it as future work.
Now for a sparse two-layer linear network with dy = 2, we focus on the case which has dense second layer. If one hidden node only has one in-degree, then based on Theorem 3, we can remove such node and consider the objective optimized with some projected data. Therefore, each hidden node should have at least two in-degree. Because one hidden node obviously leads to no bad local minima, the least sparse structure has two hidden nodes with totally eight connections (e.g., two constructions in Figure 1). We will show the existence of bad local-minima in Section 3.
2.5 GENERAL CASE WITH dy ≥ 3
We finish this section by discovering that a sub-network with its global minima might yield a spurious local minima of the original sparse network when dy ≥ 3.
Theorem 5 There exists a spurious local minima that is a global minimum of sub-network in twolayer sparse network when output dimension dy ≥ 3.
Proof: We consider the sparse structure in Figure 2 with only eight connections. The objective is
min wi
L(w1, . . . , w8) := 1
2 ∥∥∥∥∥Y −X ( w1 0 w2 w3 0 w4 )( w5 w6 0 0 w7 w8 )∥∥∥∥∥ 2
F
= 1
2 ∥∥∥∥∥Y −X ( w1w5 w1w6 0 w2w5 w2w6 + w3w7 w3w8
0 w4w7 w4w8
)∥∥∥∥∥ 2
F
.
Let X = I3 and Y = ( 1 2 0 2 10 0 0 0 4 ) . Clearly, X and Y have full column rank that is the common
assumption in previous work. Then ( w1 0 w2 w3 0 w4 ) = ( 1 0 2 2 0 0 ) , ( w5 w6 0 0 w7 w8 ) = ( 1 2 0 0 3 0 ) satisfy ∇L = 0, and L(w1, . . . , w8) = 8. In addition, for any small disturbances δi, i = 1 . . . , 8,
2L(w1 + δ1, . . . , w8 + δ8) = (δ1 + δ5 + δ1δ5) 2 + (2δ1 + δ6 + δ1δ6) 2 + (δ2 + 2δ5 + δ2δ5) 2
+ (2δ2 + 2δ6 + δ2δ6 + 3δ3 + 2δ7 + δ3δ7) 2
+ (2 + δ3) 2δ28 + (3 + δ7) 2δ24 + (δ4δ8 − 4)2
≥ (2 + δ3)2δ28 + (3 + δ7)2δ24 + (δ4δ8 − 4)2 ≥ 2 [(2 + δ3) (3 + δ7)− 4] |δ4δ8|+ 16.
Since the perturbations δi are small, we have (2 + δ3) (3 + δ7)−4 > 0. Hence, L(w1+δ1, . . . , w8+ δ8) ≥ 8, verifying the local minimizer.
However, when ( w1 0 w2 w3 0 w4 ) = √10/5 0√10 0 0 2 , (w5 w6 0 0 w7 w8 ) = (√ 10/5 √ 10 0 0 0 2 ) ,
L(w1, . . . , w8) = 0.18 < 8. Hence, a bad local minimum exists.
We underline that the bad local minimum is produced from the sub-network when w4=w8=0. Since we encounter no bad local minimum in a dense linear network, sparse connections indeed destroy the benign landscape because sparsity obstructs the decreasing path as Evci et al. (2019) mentioned from experiments.

heading: 3 BAD LOCAL MINIMUM WITH SPARSE FIRST LAYER
text: Now we turn back to the dense second layer case in Section 2.3 with dy=2, and assume X has full column rank. We give an algorithm to check the existence of spurious local minima when ∃ i 6= j, s.t.,XT−iX−j 6= 0.
Algorithm 1 Sparse-2-Opt (Z1, Z2, D): Obtain the solution of two-layer sparse linear neural network with two hidden neurons.
1: Input: Target matrix Z1, Z2 and covariance diagonal matrix D. 2: Initialize w2, d2,a2; 3: while not converge do 4: w1, d1,a1 = SV D(Z1 +D(Z2 − d2w2aT2 )); 5: w2, d2,a2 = SV D(Z2 +DT (Z1 − d1w1aT1 )); 6: end while 7: w1 = d1w1,w2 = d2w2. 8: if λ1(∇2L), λ2(∇2L) ≈ 0, λ3(∇2L) > 0 then 9: Return the solution w1,a1,w2,a2.
10: else 11: Try again from another initialization. 12: end if 13: Output: w1,a1,w2,a2.
Notice that we have no rank constraint for the Zi in Eq. (5). Suppose singular value decomposition of X−i as X−i = UiDiV Ti with Ui ∈ Rn×pi , Di ∈ Rpi×pi , Vi ∈ Rpi×pi . Since Di has full rank, we take DiViZi and DiViwi as new targets and variables. With a slight abuse of notation, then the problem becomes
min W̃ ,A
1
2 ∥∥∥∥∥ d∑
i=1
Ui ( Zi −wiaTi )∥∥∥∥∥ 2
F
. (8)
In the following, we show d = 2 is enough to give counter examples. Similarly, using the singular value decomposition of UT1 U2 as U T 1 U2 = ŪDV̄
T with a rectangle diagonal matrix D ∈ Rp1×p2 . Notice that U1, U2 are column orthogonal matrices, thus Dii ≤ 1, and |{i : Dii = 1}| equals to the overlapping columns between X−1 and X−2. Finally, the objective becomes
L(w1,w2,a1,a2) = 1
2 ‖Z1−w1aT1 ‖2F +
1 2 ‖Z2−w2aT2 ‖2F + tr[(Z1−w1aT1 )TD(Z2−w2aT2 )].
If we fix w2 and a2, we can see w1 and a1 are the best rank-1 approximation ofZ1+D(Z2−w2aT2 ), since w1 and a1 are the solution of
arg min w1,a1
‖Z1 +D(Z2 −w2aT2 )−w1aT1 ‖2F .
Similarly, w2 and a2 are the best rank-1 approximation of Z2 +DT (Z1 −w1aT1 ). Empirically, we use alternating update method to find the solution in Algorithm 1 for two blocks, where SV D(·) is a classical method getting the largest singular value and the corresponding singular vectors.
Since each update does not increase the loss, this makes the convergence of sequence w1,a1,w2,a2. Once the algorithm converges, the first-order condition is satisfied and two eigenvectors with zero eigenvalue of the Hessian matrix are decided. Moreover, we can also prove that the convergent solution is indeed a local minima (detail see Appendix B). Otherwise, we examine a local minimum using gradient descent or other optimization method started with noise, if necessary.
Based on Algorithm 1, we find several cases with bad local minima including the overlapping case (∃i, Dii = 1). The results are shown in Table 1. We observe distinct gaps between the local minima because our choice of elements in the Zi is small. In the non-overlapping setting, the algorithm reaches the local min quickly and shows several different examples. As for the overlapping setting, a simple construction is leaving out the repeated feature away with zero items in the Zi, though we also show bad-min applied with the overlapping data feature in Row 3 in Table 1.
It is interesting to note that for d = 2, only at most two local minimum are found, and we can easily broaden the alternating update method into general d case in Appendix D, that will also verify similar observation: at most d local minimum produced by a sparse-first-layer network with hidden d nodes, which leaves as future work. Overall, sparsity breaks the original matrix structure, leading to additional low rank constraint in this case, and still cuts out the decreasing path in the original fully-connected network.
Additionally, a descent algorithm still will diverge to infinity. For instance, the example in Appendix A shows that there is a sequence diverging to infinity while the function values are decreasing and convergent.

heading: 4 LANDSCAPE OF DEEP SPARSE LINEAR NETWORKS
text: In this section, we briefly extend Theorems 1 and 2 to deep sparse linear networks and leave the proof in Appendix F. The intuition is that deep linear networks have similar landscape property as the shallow case (Lu & Kawaguchi, 2017; Eftekhari, 2020). However, understanding the landscape of an arbitrary deep sparse linear network is still complicated.
Theorem 6 For a deep sparse linear neural network with scalar output (dy = 1) and any sparse structure, every local minimum is a global minimum.
The proof intuition can be described by induction based on shallow linear networks. The above theorem shows that sparsity introduces no bad-min when applied with scalar target. In addition, we give a simple choice for obtaining a global minimizer below.
How to obtain a global minimizer in scalar case: One way is to set the first-layer weights as the global minimizer in the two-layer case with ai = 1, then the remaining layers uniformly distribute the output of each node to the next layer. For example, if one node has k output connections, then each connection assigns weight 1/k. Hence, the sum of each layer output remains the best solution to approximate target Y (see the right graph of Figure 2 for example).
Theorem 7 For a deep sparse linear neural network with a sparse first layer and dense other layers, assume that X,Y have full column rank, and ∀ i 6= j, XT−iX−j = 0. If di ≥ min{d1, dy},∀i ≥ 1, where di is the hidden width in the i-th layer, then every local minimum is a global minimum.
Note that under our assumption di ≥ min{d1, dy},∀i ≥ 1, the deep linear network we study has the same solution as the shallow linear network when the first-layer weight fixed. Hence, the optimal value for our objective function is equal to the optimal value of the shallow network problem.

heading: 5 DISCUSSION
text: We have discussed the landscape of sparse linear networks with several arguments. On the positive side, spurious local minimum does not exist when the objective applied with scalar target, or with separated first layer and orthogonal training data. On the negative side, we have discovered the bad local minimum when the previous conditions are violated in a general sparse two-layer linear network, that is, one is generated from low rank constraint, another is produced from sub-sparse structure. Both the cases show that sparsity cuts out the decreasing path in the original fully-connected network. Since dense linear networks possess benign landscape, we have concluded that sparsity or network pruning destroys the favourable solutions. However, some heuristic algorithms combining training and pruning still work well in practice, leading to mystery of modern network pruning methods and sparse network design. Other interesting questions for future research include understanding the gap between global minimum and spurious local minimum, or showing a similar performance of bad-min, particularly, combining with pruning algorithms.

heading: A DECREASING PATH OF SPARSE LINEAR NETWORK WITH SPARSE FIRST LAYER
text: In addition, there still exists decreasing path to infinity:
min wi
L(w1, . . . , w8) : = 1
2 ∥∥∥∥∥Y −X ( w1 0 w2 w3 0 w4 )( w5 w6 w7 w8 )∥∥∥∥∥ 2
F
= 1
2 ∥∥∥∥∥Y −X ( w1w5 w1w6 w2w5 + w3w7 w2w6 + w3w8
w4w7 w4w8
)∥∥∥∥∥ 2
F
(9)
X = I3, Y = ( 1 0 0 1 1 1 ) , Choose (w1, w2, w3, w4, w5, w6, w7, w8) = (− 1√k ,− √ k, 1, 1, 1√ k , 0, 1, 1), with k ∈ N+. then 2L(w1, . . . , w8) = ( 1k + 1) 2 > 1 decreases when k increases. Since minwi L(w1, . . . , w8) = 0, hence we get a decreasing path to infinity, but not a global minimum.

heading: B ALGORITHM ANALYSIS
text: We built algorithm guarantee in the following:
First, since each update step, the objective doesn’t increase, then the algorithm will converge.
Second, we verify that the convergent solution (w∗1,a ∗ 1,w ∗ 2,a ∗ 2) satisfy zero gradient. Recall the first-order condition:
− ∂L ∂w1
= ( Z1 −w1aT1 +D(Z2 −w2aT2 ) ) a1 = ( Z1 +D(Z2 −w2aT2 ) ) a1 − aT1 a1w1,
− ∂L ∂a1
= ( Z1 −w1aT1 +D(Z2 −w2aT2 ) )T w1 = ( Z1 +D(Z2 −w2aT2 ) )T w1 −wT1 w1a1,
− ∂L ∂w2
= ( Z2 −w2aT2 +DT (Z1 −w1aT1 ) ) a2 = ( Z2 +D T (Z1 −w1aT1 ) ) a2 − aT2 a2w2,
− ∂L ∂a2
= ( Z2 −w2aT2 +DT (Z1 −w1aT1 ) )T w2 = ( Z2 +D T (Z1 −w1aT1 ) )T
w2 −wT2 w2a2. (10)
Notice that w∗1,a ∗ 1 is the best rank-1 approximation of Z1 + D(Z2 − w∗2a∗T2 ), and w∗2,a∗2 are the best rank-1 approximation of Z2 + DT (Z1 − w∗1a∗T1 ). Then we have already got a solution (w∗1,a ∗ 1,w ∗ 2,a ∗ 2) with zero gradient.
Third, we verify that the convergent solution is a local minimizer through the conditions we checked. Set r1 = Z1 +D(Z2 −w2aT2 ), r2 = Z2 +DT (Z1 −w1aT1 ). Then
∇2L(w1,a1,w2,a2) =  aT1 a1Ip1 −r1 + 2w1aT1 aT1 a2D Dw2aT1( −r1 + 2w1aT1 )T wT1 w1Idy a2w T 1D w T 1Dw2Idy
aT1 a2D T DTw1a T 2 a T 2 a2Ip2 −r2 + 2w2aT2 a1w T 2D T wT1Dw2Idy ( −r2 + 2w2aT2 )T wT2 w2Idy  (11)
Set H∗ := ∇2L(w∗1,a∗1,w∗2,a∗2). Observe that( w∗T1 ,−a∗T1 ,0T ,0T ) H∗ = 0, ( 0T ,0T ,w∗T2 ,−a∗T2 ) H∗ = 0,
showing that H∗ has zero eigenvalue with at least two eigenvectors v1 = ( w∗T1 ,−a∗T1 ,0T ,0T )T and v2 = ( 0T ,0T ,w∗T2 ,−a∗T2 )T .
Suppose the third smallest eigenvalue is λ3 ≥ > 0, then for any direction v with ‖v‖2 = 1, we have v = α1v̄1 + α2v̄2 + α3v̄3 with v3⊥v1,v3⊥v2, ∑3 i=1 α 2 i = 1, and w̄ := w/‖w‖2.
If α3 6= 0, then vHv = α23v̄3Hv̄3 ≥ α23λ3 ≥ α23 ≥ 0. Otherwise, we set v = δ1v1 + δ2v2 with small δ1, δ2 as perturbation, and the perturbed parameters are notated as w̃1, ã1, w̃2, ã2 = (1− δ1)w∗1, (1− δ2)w∗2, (1 + δ1)a∗1, (1 + δ2)a∗2, which yields
L(w̃1, ã1, w̃2, ã2) = ‖X1 ( Z1 − (1− δ21)w1aT1 ) +X2 ( Z2 − (1− δ22)w2aT2 ) ‖2F
= ‖X1 ( Z1 −w1aT1 ) +X2 ( Z2 −w2aT2 ) ‖2F + ‖δ21w1aT1 + δ22w2aT2 ‖2F
+ 2δ21 tr[ ( w1a T 1 )T ( r1 −w1aT1 ) ] + 2δ22 tr[ ( w2a T 2 )T ( r2 −w2aT2 ) ]
= ‖X1 ( Z1 −w1aT1 ) +X2 ( Z2 −w2aT2 ) ‖2F + ‖δ21w1aT1 + δ22w2aT2 ‖2F
= L(w1,a1,w2,a2) + ‖δ2α21w1aT1 + δ2α21w2aT2 ‖2F ≥ L(w1,a1,w2,a2). (12)
Third equality holds for the rank-1 approximation of the solution. Hence, the convergent solution is a local minimizer.
Fourth, due to numerical error, we can not obtain exact convergent solution, but we are able to obtain approximate solution (wt1,a t 1,w t 2,a t 2) after t iterations with L (w t 1,a t 1,w t 2,a t 2) − L (w∗1,a ∗ 1,w
∗ 2,a ∗ 2) ≤ 2, and then use Weyl’s inequality (Safran & Shamir, 2018, Theorem 2),∣∣λi(∇2L(wt1,at1,wt2,at2))− λi(∇2L(w∗1,a∗1,w∗2,a∗2))∣∣ < O( ),
where λi(H) is the i-th smallest eigenvalue of the real symmetric matrix H . Therefore, if the approximate solution is approximate positive semi-definite with a large third smallest eigenvalue, we conclude the convergent solution is a local minimizer.

heading: C USELESS CONNECTIONS AND NODES IN SPARSE NETWORK
text: In this section, we explain several kinds of unnecessary connections suffered from sparsity or network pruning.
Hidden layer 1
Hidden layer 2 Input layer
Output layer
1. Zero out-degree I: if a node have zero out-degree, such as h(2)1 in Figure 3, we can eliminate the input connections.
2. Zero out-degree II: if a node have zero out-degree when removed output connections in latter layers, such as h(1)1 in Figure 3. Though it owes one output connection, the connected node h(2)1 is zero out-degree, hence the connection can be removed, leading to zero outdegree. We can eliminate the input connections of h(1)1 as well.
3. Zero in-degree I: if a node have zero in-degree, such as h(2)4 and h (1) 4 in Figure 3, we can
eliminate the output connections, but notice that when the node has a bias term, then we can not remove output connections since the bias constant will still propagate to subsequent layers.
4. Zero in-degree II: if a node have zero in-degree when removed input connections in former layers, such as h(2)3 in Figure 3. Though it owes one input connection, the connected node h (1) 4 is zero in-degree, hence the connection can be removed, leading to zero in-degree. We
can eliminate the output connections of h(2)3 as well.
D GENERAL d BLOCKS ALGORITHM
Algorithm 2 Sparse-d-Opt (X1, . . . , Xd, Z1, . . . , Zd): Obtain the solution of two-layer sparse linear neural network with d hidden neurons.
1: Input: Input matrix X1, . . . , Xd. Target matrix Z1, . . . , Zd; 2: Initialize wi, di,ai, i = 2, . . . , d; 3: while not converge do 4: for i = 1, . . . , d do 5: wi, di,ai = SV D(Zi + ∑ j 6=iX T i Xj(Zj − djwjaTj )); 6: end for 7: end while 8: wi = diwi, i = 1, . . . , d. 9: if λ1(∇2L), . . . , λd(∇2L) ≈ 0, λd+1(∇2L) > 0 then
10: Return the solution wi,ai, i = 1, . . . , d. 11: else 12: Try again from another initialization. 13: end if 14: Output: wi,ai, i = 1, . . . , d.
The analysis that the convergent solution is a local minimizer is similar to d = 2, so we are not going to repeat the details. We list some examples searched for d > 2 below.
d = 3: Target: Z1 = (
0 0 0 1
) , Z2 = ( 1 0 1 1 ) , Z3 = ( 1 0 −1 −1 ) .
Training data: XTX =  1.0 0.0 −0.088 −0.599 −0.234 0.178 0.0 1.0 −0.163 0.429 −0.529 0.431 −0.088 −0.163 1.0 −0.0 0.558 0.193 −0.599 0.429 −0.0 1.0 −0.357 −0.244 −0.234 −0.529 0.558 −0.357 1.0 −0.0 0.178 0.431 0.193 −0.244 −0.0 1.0  Local minimum found:

heading: E MISSING PROOFS FOR SECTION 2
text: E.1 PROOF OF THEOREM 3
Proof: Suppose the j-th node has full out-degree and one in-degree, so that w−j ∈ R. We treat objective with fixed other weights and only consider optimizing w−j ,aj .
min wj ,aj
`(wj ,aj) = 1
2 ∥∥∥Ỹ −X−jwjaTj ∥∥∥2 F , Ỹ := Y − ∑ i6=j X−iw−ia T i . (13)
Based on the proof of scalar case, a local minimizer (w∗j ,a ∗ j ) of `(wj ,aj) must satisfy the condition
XT−j ( Ỹ −X−jw∗ja∗Tj ) = 0, showing that `(w∗j ,a ∗ j ) = 1 2‖ ( I − PX−j ) Ỹ ‖2F . Therefore, the objective with remaining weights becomes:
min w−i,ai,i6=j
1
2 ∥∥∥∥∥∥(In − PX−j)Y − ∑ i 6=j ( In − PX−j ) X−iw−ia T i ∥∥∥∥∥∥ 2
F
. (14)
We define (( In − PX−j ) XSj , ( In − PX−j ) Y )
as new training dataset which is the projection into the orthogonal complement ofX−j , and remove some elements in w−i corresponding to the column in X−j . Moreover, if X has full column rank, then projected data ( In − PX−j ) XSj still has full column rank. Hence, removing the above connections doesn’t affect the spurious local minima since these connections preserve certain solution.
E.2 PROOF OF THEOREM 4
Proof: The original loss function can be formulated as below,
2L(W̃ , Ã) = ∥∥∥∥∥∥Y1− ∑ i∈R1 X−iw−iai1− ∑ j∈R X−jw−jaj1 ∥∥∥∥∥∥ 2
F
+ ∥∥∥∥∥∥Y2− ∑ i∈R2 X−iw−iai2− ∑ j∈R X−jw−jaj2 ∥∥∥∥∥∥ 2
F
.
Under similar analysis as scalar case,
∀i ∈ R1, XT−i Y1 − ∑ i∈R1 X−iw−iai1 − ∑ j∈R X−jw−jaj1  = 0. ∀i ∈ R2, XT−i
Y2 − ∑ i∈R2 X−iw−iai2 − ∑ j∈R X−jw−jaj2  = 0. Hence, w−i1ai11 ... w−ijaij1 ...
w−i|R1|ai|R1|1
 = ( X−i1 , · · · , X−ij , · · · , X−i|R1| )+Y1 −∑ j∈R X−jw−jaj1
 , ij ∈ R1.  w−i1ai12 ... w−ijaij2 ...
w−i|R2|ai|R1|1
 = ( X−i1 , · · · , X−ij , · · · , X−i|R2| )+Y2 −∑ j∈R X−jw−jaj2
 , ij ∈ R2. Then the objective becomes:∥∥∥∥∥∥(In − PX−T1 ) Y1 −∑ j∈R X−jw−jaj1 ∥∥∥∥∥∥ 2
2
+ ∥∥∥∥∥∥(In − PX−T2 ) Y2 −∑ j∈R X−jw−jaj2 ∥∥∥∥∥∥ 2
2
.
We can see the objective is separated into two parts with shared sparse first-layer weights. Notice that if i /∈ T1, then Xi ∈ XT1 , hence ( In − PX−T1 ) Xi = 0. Therefore, we simplify the problem as
min W̃ ,Ã
L(W̃ , Ã) = 1
2 ∥∥∥∥∥∥(In − PX−T1 ) Y1 −∑
i∈T1
Xi ∑
j:i/∈Sj
wijaj1 ∥∥∥∥∥∥ 2
2
+ 1
2 ∥∥∥∥∥∥(In − PX−T2 ) Y2 −∑
i∈T2
Xi ∑
j:i/∈Sj
wijaj2 ∥∥∥∥∥∥ 2
2
.
(15)
Use previous analysis again on T1 \ T2 in first output dimension and T2 \ T1 in second output dimension since no overlap in parameters by the condition U(T1 ∩ T2) ∩ U(T1 \ T2) = ∅ and U(T1 ∩ T2) ∩ U(T2 \ T1) = ∅. Therefore, we simplify the problem again as
min W̃ ,Ã
L(W̃ , Ã) = 1
2 ∥∥∥∥∥∥ ( In−P(In−PX−T1 )XT1\T2 )( In−PX−T1 )Y1− ∑ i∈T1∩T2 Xi ∑ j:i/∈Sj wijaj1 ∥∥∥∥∥∥ 2
2
+ 1
2 ∥∥∥∥∥∥ ( In−P(In−PX−T1 )XT2\T1 )( In−PX−T2 )Y2− ∑ i∈T1∩T2 Xi ∑ j:i/∈Sj wijaj2 ∥∥∥∥∥∥ 2
2
.
Using the fact that (In − PW1) (In − PW2) = In−P(W1,W2) if WT1 W2 = 0. Hence the remaining problem is same as
min W̃ ,Ã
L(W̃ , Ã) = 1
2 2∑ k=1 ∥∥∥∥∥∥(In − PX−T1∩T2 ) Yk − ∑ i∈T1∩T2 Xi ∑ j:i/∈Sj wijajk ∥∥∥∥∥∥ 2
2
.
Therefore, the remaining network structure has dense second layer.

heading: F MISSING PROOFS FOR SECTION 4
text: The objective of a deep linear network with squared loss is
min W (1),...,W (L)
1 2 ‖Y −XW (1) · · ·W (L)‖2F , (16)
where the i-th layer weight matrix W (i) ∈ Rdi−1×di , d0 = dx, dL = dy , Data matrix X ∈ Rn×dx , Y ∈ Rn×dy . We adopt S(i)j = {k : W (i) kj = 0} as pruned dimensions in j-th column of W (i). Besides, W (i)j,−S as the remaining j-th column in i-th layer weight which leaves out pruned
dimension set S. For simplification, we denote w(i)−j = w (i) j,−S(i)j ∈ R
( di−1−|S(i)j | ) , w(i)jk = W (i) jk ,
and W̃ (i) as the pruned weight matrix with several zero elements as before.
F.1 PROOF OF THEOREM 6
Proof: Using induction. Base on Theorem 1, we have already proof two layer case. If the result holds for (L− 1)-layer sparse linear network, we consider L layer case. We denote Xnew := XW̃ (1) as new training set, and ` := Y −XW̃ (1) · · · W̃ (L). Then based on inductive assumption, `TXnew = 0, showing that
`TX−iw (1) −i = 0, ∀1 ≤ i ≤ d1. (17)
Combined with first-order condition:
∂L
∂w (1) −i
= −`TX−i(W̃ (2) · · · W̃ (L))i = 0.
If (W̃ (2) · · · W̃ (L))i 6= 0, then `TX−i = 0, which satisfies the global minimizer condition. Otherwise, any value of w(1)−i doesn’t change the loss since the forward path already contribute zero to the final output. Hence, arbitrary choice of w(1)−i owes same objective value. Thus, from Eq. (17), we still obtain `TX−i = 0. Thus any local minimum is a global minimum for the pruned sparse model.
F.2 PROOF OF THEOREM 7
Proof: Since ∀ i 6= j, X−i, X−j share no same columns and XTX = Id, then ∀ i 6= j, XT−iX−j = 0. Besides, from our assumption ∩mj=1Sj = ∅, then ∩mj=1Sj = {1, . . . , d}, meaning that (X−1, . . . , X−d) is X with different arrangement of columns. Hence
Y = PXY + (I −PX)Y = X(XTX)−1XTY + (I −PX)Y , d∑
i=1
X−iZi + (I −PX)Y, (18)
Set W (2) = [a1, . . . ,ad1 ] T , then the objective becomes
1
2 d1∑ i=1 ‖Zi −w−iaTi W (3) · · ·W (L)‖2F .
We set X̃ = XW̃ (1) = (X−1w−1, . . . , X−d1w−d1). Now we show the following problems have same local minimizer condition for w−1.
(P) L(W̃ (1),W (2), . . . ,W (L)) = 1
2 ∥∥∥Y − X̃ (W (2) · · ·W (L))∥∥∥2 F ,
(P1) L2(W̃ ,A) = 1
2 ∥∥∥∥∥Y − d1∑ i=1 X−iw−ia T i ∥∥∥∥∥ 2
F
.
(19)
If there is a local minimizer w−1, . . . ,w−d1 6= 0, for problem (P), since di ≥ min{d1, dy},∀i ≥ 1 and X̃, Y have full column rank, then based on Theorem 2.3 in Lu & Kawaguchi (2017), a local minimizer of L(W̃ (1),W (2), . . . ,W (L)) is obtained when
W (2) · · ·W (L) = ( X̃T X̃ )−1 X̃TY.
Notice that X̃T X̃ = diag(wT−1w−1, . . . ,w T −d1w−d1). Then the objective is simplified as
2L(W̃ (1)) = ∥∥∥∥Y − X̃ (X̃T X̃)−1 X̃TY ∥∥∥∥2 F = ∥∥∥∥∥Y − d1∑ i=1 (X−iw−i)(X−iw−i) TY wT−iw−i ∥∥∥∥∥ 2
F
= d1∑ i=1 ∥∥∥∥X−iZi − (X−iw−i)(X−iw−i)TX−iZiwT−iw−i ∥∥∥∥2 F
= d1∑ i=1 ∥∥∥∥X−iZi − X−iwT−iw−iZiwT−iw−i ∥∥∥∥2 F
(20)
For problem (P1), similarly, a local minimizer of L2(W̃ ,A) is obtained when (X−jw−j) T ( Y − ∑d1 i=1X−iw−ia T i ) = 0. Then aTj = (X−jw−j) TY
wT−jw−j , showing same loss
objective as
2L2(W̃ ) = ∥∥∥∥∥Y − d1∑ i=1 (X−iw−i)(X−iw−i) TY wT−iw−i ∥∥∥∥∥ 2
F
= d1∑ i=1 ∥∥∥∥X−iZi − (X−iw−i)(X−iw−i)TX−iZiwT−iw−i ∥∥∥∥2 F = 2L(W̃ (1)).
(21)
Finally, based on Theorem 2, every local minimum of (P1) is a global minimum. Hence every local minimum of (P) is a global minimum.
If there exists i0, such that w−i0 = 0, we show that Zi0 = 0 below. Without loss of generality, we assume i0 = 1, then the value of a1 does not affect the objective, we take a1 = 0 as well. In order
to show the result, we only perturb w−1,a1, W (3), . . . ,W (L) into w−1 + ∆w,a1 + ∆a,W (3) + ∆3, . . . ,W (L) + ∆L and analyze the difference of loss as ∆L. We set
∆W , L∏
i=3
( W (i) + ∆i ) − L∏ i=3 W (i), W o , L∏ i=3 W (i). (22)
Then the perturbation leads to
2∆L(∆w,∆a,∆W ) = ‖Z1 −∆w∆aT (W o + ∆W ) ‖2F − ‖Z1‖2F + ∑ i 6=1 ‖Zi −w−iaTi (W o + ∆W ) ‖2F − ‖Zi −w−iaTi W o‖2F
= −2tr[ZT1 ∆w∆aT (W o + ∆W )] + ‖∆w∆aT (W o + ∆W ) ‖2F − 2 ∑ i 6=1 tr[∆WTaiw T −i ( Zi −w−iaTi W o ) ] + ‖w−iaTi ∆W‖2F .
(23)
Applying the first case to the remaining parameters excluding w−1 and a1 (If there are several w−is are zero, we can leave them all out), we have
aTi W o =
(X−iw−i) TY
wT−iw−i =
(w−i) TZi
wT−iw−i ,
which agrees with wT−i ( Zi −w−iaTi W o ) = 0, i 6= 1.
Hence the second term in the final row of Eq. (23) is zero. Besides, let us note the first-order term of ∆w, showing that tr[ZT1 ∆w∆a
T (W o + ∆W )] = 0. Otherwise, given w−1 = Θ(t−1),a−1 = Θ(t−1), ∆W = Θ(t−3), as t→∞, the sign in the final expansions of Eq. (23) depends on the fist term that is indefinite.
Therefore, ∆a (W o + ∆W )ZT1 = 0, then (W o + ∆W )ZT1 = 0, leading to W oZT1 = 0 and ∆WZT1 = 0.
In view of expression ∆W , it holds that
∆WZT1 = d1∑ i=3 ( W (3) · · ·W (i−1)∆iW (i+1) · · ·W (L) ) ZT1 + . . .
= L−2∑ t=1 ft(∆3, . . . ,∆L)Z T 1 ,
(24)
where ft(∆3, . . . ,∆L) is the sum of the product in W (3), . . . ,W (L),∆3, . . . ,∆L that contains exactly t different ∆is. Then from small-order terms to high-order terms, we obtain ft(∆3, . . . ,∆L)Z1 = 0. It follows from fL−2 = ∆3 · · ·∆L, di ≥ min{d1, dL}, and the arbitrary of ∆3 · · ·∆L, we get Zi = 0. Finally, when Z1 = 0, It is evident that w1 = 0 already satisfies the global minimizer condition since the objective is separated as ∑d1 i=1 ‖Zi−w−iaTi W (3) · · ·W (L)‖2F . This completes the proof.

Review summaries:
This paper studies the loss landscapes of sparse linear networks. It proves that under squared loss, (1) spurious local minimum does not exist when the output dimension is one, or with separated first layer and orthogonal training data; and (2) for two-layer sparse linear networks, the good property in (1) does not exist anymore when the conditions are violated. The authors also report experimental results to show that two-layer sparse linear networks with two hidden neurons have spurious local minima.

This paper studies the optimization landscape of (deep) sparse linear networks. The study of sparse neural networks is well motivated: on the one hand, there is a lot of experimental evidence that the loss of the trained network does not decrease much after removing a large subset of the connections; on the other hand, there is little theoretical evidence of what makes this behaviour possible (or how to provably construct sparse networks from dense ones). As a result, an investigation of the optimization landscape of sparse networks, even in the simple case of a linear activation function, is timely and interesting to the ICLR community, since it can potentially shed light on the questions above.