On the Landscape of Sparse Linear Networks
Authors: Dachao Lin
Ruoyu Sun
Zhihua Zhang
Venue:  (2021)
Keywords: theory
sparse network
landscape

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.

Under review as a conference paper at ICLR 2021
ON THE LANDSCAPE OF SPARSE LINEAR NETWORKS
Anonymous authors
Paper under double-blind review
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 fol- lowing statements for the squared loss objective of general sparse linear neural networks: 1) every local minimum is a global minimum for sealar output with any sparse structure, 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 di- mensions 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.
INTRODUCTION
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 be highly overparameterized, making them computationally expensive with large amounts of memory and computational power. For example, it may take up to weeks on 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 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-ae results under high levels of sparsity (Han et al. 2015b Gale al. 2019 Louizos al. 2017a). Modern sparse networks are mainly obtained from network pruning (Zhu & Gupta 2017 Lee et al. 2018 [iu et al., 2018 Frankle & Carbin 2018), which has been the subject of great deal of work in recent years. How- ever, training sparse network with fixed sparsity patterns 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 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 net- works. We need to emphasize that dense deep linear networks already satisfy that every local min- imum is global minimum under mild conditions (Kawaguchi] 2016 Lu & Kawaguchi (201)) 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, also briefly show that

---

Under review as a conference paper at ICLR 2021
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 ncnlsc 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 we briefly generalize the results from shallow to deep sparse linear networks. Some proofs are in Appendix.
1.1 RELATED WORK
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, only briefly survey the works most related to ours.
Local minima Global. The landscape of linear network date back to Baldi & Hornik (1989) proving that shallow linear neural networks do not suffer from bad local minima. KKwaauuchi (2016) generalized same results to deep linear neural networks, and subsequent several works (Arora al, 2018 Du & Hul 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 al. 2017 Safran & Shamir, 2018 Yun et al.) 2018) show that spurious local minima can happen even in two-layer network with population empirical loss, some specific two-layer and difficult to generalize multilayer cases. Another line of works (Arora et al.] 2018 |018|AAllen-2/ Allee-Zhu et al. (2018) Du & Hu 2019)
general
Du al. 2018 Li al. 2018 Mei al.] 20188) 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 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 dif- ficulty. 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. (201)) 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 abun- dant methods (Molchanov et al. 2017 Louizos al. 2017b] Lee et al. 2018
& Idelbayev| 2018) for choosing weights or sparse network structure while achieving similar perfor- mance. 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 tar- get network, providing guarantee for 'good' sparse networks. Some works analyze convolutional network (Shalev-Shwartz et al. 2017 Du et al. 2018) specific sparse structure. [Brutzkus & Globerson (2017) analyze overoverlg and overlapping structure as we do, but with weight sharing to simulate CNN-type structure, and under macher-student setting with population risk. We do not follow CNN-type network but in general sparse networks, though still linear, to conclude straightforward results.
2

---

Under review as a conference paper at ICLR 2021
2 LANDSCAPE OF SHALLOW SPARSE LINEAR NETWORKS
2.1 PRELIMINARIES AND NOTATION
We use bold-faced letters (e.g., w and a) to denote vectors, capital letters (e.g., W [we]]] and A (ay]) for matrices. Let Px be the orthogonal projection to the column space of the matrix X, real symmetric matrix H.
and (H) is the i-th smallest cigenvalue
We consider the training samples and their outputs as {(x,, ) C Cd x Rd,, which may come from unknown distribution D. We form the data matrices X [x]..... x,l E Raxx, and
Y = [y IRxxdy, respectively. our analysis in Sections and we consider
two-layer (sparse) linear neural network with squared loss:
min L(W, = 1 -XWA W.
(1)
where the first layer weight matrix W [w....., wal E Rddx and the second layer weight matrix A (a),..., az)² RRddd After weights pruning sparsity constraint, many weights parameters become zero and would not be updated during retraining. We Sy := u 0} as pruned dimensions in the j-th column of W, and -j == Sj [d where [d] := (l....,de d]. In addition, wj.s denotes the sub-vector of w, choosing the positions in S, Xs the sub-matrix of X choosing the column indices in S.
We let Pj = d₂ - |Syl, where [S] is the cardinality of the set S. Then w,--S, E R is the remaining j-th column first layer weight which leaves out pruned dimension set Sj. Similarly, X-s, E *xp means the remaining data matrix connected j-th node in the first layer.
Finally, for simplicity, we denote with several zero elements not updated all along, no ambiguity.
W-j w,, and (-) as the pruned layer weight
Before we begin, a small note on the sparse structure we concern: there may have unnecessary connections and nodes, such as 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. ng S 0.
2.2 SCALAR CASE
In the scalar case, assume dy = 1. We then simplify = aa)) When pruning any weight in the second layer, the output of the i-th node in the first layer contribute zero to final output. Hence w, can also pruned. Without loss of generality, we assume second layer parameters are not pruned. After pruning several parameters, the original problem becomes
2
01W
min L(W, =) Y (X-1, X-t, w-
X-a)
:
a.
Theorem For two-layer linear neural network with scalar output and any sparse structure, every local minimum is a global minimum.
Proof: From Eq. (2) if local minimizer satisfies = 0 for some < < d, then based on the second order condition for a local minima, we have
0 L da? al iw_;
8 L da;ōw² aL
Σ 0,
(3)
dw
3

---

Under review as a conference paper at ICLR 2021
Input layer
Hidden layer
Output layer
Input layer
Hidden layer
Output layer
211
42
h2
1/1
272
43
122
(1)
1/2
ft/2
(1)
1/2
33
T4
Figure 1: Sparse network without (left)/ with (right) overlapping filters the first layer.
which implies that
w N_,_; -X, Wi
- -(y-Ei
- X-ww X-1
2 0.
(4)
X_ >x11 X X_:W-:0;
Then x_, EY- X- = 0, which the global minimizer condition w-,ag
Otherwise, a; # then from the first-order condition for local minima,
aL
= ax
Y
X
W
0,
1=1
showing that XT, (Y -Y-Ei= X_ww-aa O, which also gives the global minimizer condition of w_,a, Hence every local minimum global minimum.
2.3 NON-SCALAR CASE WITH DENSE SECOND LAYER
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 L(W, A) = 1 Y Σ wi
x B- 0
(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 degure[ and orthogonal data feature meet requirements.
Theorem For a two-layer sparse linear neural network with dense second layer, assume that X full column rank, and v i + j. XT, 0. Then every local minimum is global.
Since V i # j. X_,__ columns. Additionally, from our assumption S 0, we have nz [dz], meaning that (X 1, ................................ X-a) is X with different arrangement of columns. Hence,
Proof:
0 and X is full column rank, X_ and X_, share no same
Y P + - Px)Y -XX"= Px)Y x (T Px)Y, (6)
1=1
where Z, (Xx"))-X"X)) -s, is the sub-matrix choosing the row indices in -S:- Then we only need to consider the objective:
1 d
min L(W A) = Σ W-i.a;
x- (2,
w_,a,)) (0----,a
X_ (Zi - w- (7)
=
4

---

Under review as a conference paper at ICLR 2021
Input layer
Hidden layer 1
Output layer
Input layer
Hidden layer
Hidden layer
Hidden layer 3
Output layer
1/2
h
1/2
21
W/
10
81
211
1/3
0/2
W/6
12
22
h22
1/3
22
1/2
222
11
1/3
112
(1)
0/7
h3
1/3
h3
1/3
1/3
33
1/4
Wg
0
23
1/3
4
Figure 2: Left: spurious local minimum exists in sparse línear network with dy 3 shown in above, that is the global minimum of sub-network. Right: one simple weight assignment for obtaining the global minimum in deep sparse linear network with scalar output.
We will see that the objective has already been separated into d parts, while each part is two-layer dense linear network with full column rank data matrix. Based on Theorem 2.2 in Lu & Kawaguchi (2017) Eckart- Young-Mingg every local minimum is global minimum.
theorem (Eckart & Young 1936;
Mirsky 1960), we obtain that
Additionally, we need to explain the assumption that non-overlapping filters the first layer involves convolution networks (Brutzkus & Globerson 2017) if weight sharing is used. Otherwise, we will showa a bad local minima exists when the first layer is overlapped or training data 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 d, = 2. We first prove that some connections still owe common benign landscape which can be removed.
Theorem For a sparse two-layer network, a node with full out-degree and one in-degree can be removed if 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, 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 Node and Node 2, and the hidden nodes which have only one connection to the output layer as R, and R2 while the remaining full connection set as R. Set Ti = NjER, Sy. To Sj. We define U(T) (j wij + 0, T} the hidden node connected with data feature in T. When the hidden node sets connected to Ti and To satisfy the condition below, we are able simply the sparse structure into the dense layer case.
Theorem For sparse two-layer linear network with dy 2, if U(T T2) nu(TI T2)= and U(T n T2) (T( Ti) = 0, 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 Additionally, from the proof of Theorem 4 the objective is converted into two objectives with weight sharing in the first layer the assumption does not meet. Weight sharing structure has been shown in some related work (Shalev-Shwarte et al., 2017 Brutzkus & Globerson) 2017). so we do not give detailed description and leave it future work.
5

---

Under review as a conference paper at ICLR 2021
Now for sparse two-layer linear network with dy = 2, focus on the which has dense second layer. one hidden node only has one in-degree, then based on Theorem we can remove such node and consider the objective optimized with 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 J. We will show the existence of bad local-minimg in Section
projected data. Therefore, each hidden
2.5 GENERAL CASE WITH d, 23 3
We finish this section by discovering that sub-network with its global minima might yield spuri- ous local minima of the original sparse network when dy 2 3.
Theorem There exists a spurious local minima that is global minimum of sub-network in two- layer sparse network when output dimension dy 23
Proof: We consider the sparse structure in Figure 2 with only eight connections. The objective is
min L(w1,.... ,....... wx)
wa
2
1
Y - X
W1 W2
0
wis
0
W66
WT
W0s
0
F
1
[0 Wi
W1 WG
Y X
W2 W0 0
W2 + W3
Wy
2
W4
W4
F
1
2
0
Let X = Ia and Y
10
4)
Clearly, and Y have full column rank that is the common
0
0
[w
0
1 0
assumption previous work. Then
W2
W3 = 2
2
2
105
01
0
0
0
WP
satisfy L = 0, and L(w wg) = 8. In addition, for any small disturbances 6;, 1...,8, 8,
2L(w1 W1 + _1,..., ws + 68) (61 + (26 + 0166)² (82 +6g + 8265)²
+ (26, + +2: 30, 25, + 6357)2
+ +2++))
+ (646s - 4)2
2 +3+ + (516g - 4)2
2 2
(3+ (3+ 4| 8 16.
Since the perturbations 5, are small, we have (2 + 53) (3 + 57) 0. Hence, I[ + (( +.,,..., u 5g) > 8, verifying the local minimizer.
W1
0
10/5 0
0
= (V10/5
v10 0)
However, when
W2
W3
=
V10
0
0
W44
2
[(wi...... wg) 0.18 < 8. Hence, a bad local minimum exists.
We underline that the bad local minimum is produced from the sub-network when w =0. Since we encounter no bad local minimum dense linear network, sparse connections indeed destroy the benign landscape because sparsity obstructs the decreasing path as Evvi et al. (2019) mentioned from experiments.
3 BAD LOCAL MINIMUM WITH SPARSE FIRST LAYER
Now turn back to the dense second layer case in Section 2.3 with =2, and assume X has full column rank. We give an algorithm to check the existence of spurious local minima when 3 i * j, s.L., X2,X X --j O.

---

Under review as a conference paper at ICLR 2021
Algorithm Sparse-2-Opt (Zi, Z2, D): Obtain the solution of two-layer sparse linear neural net-
work with two hidden neurons.
1: Input: Target matrix Zı, Z2 and covariance diagonal matrix D.
2: Initialize W2, d2, 02:
3: while not converge do
4: W1, W1,d1, a1 = SV (22 + D d2w2a2)
5: W2, dg, a2 SVD(Z2 D (21 d]wia
6: end while
7: W1 di W1 W2 d.
8: if LV) ( (V ~ 0. A3( L) > 0 then
9: Return the solution W1, 01 W2, 02
10: else
11: Try again from another initialization.
12: end if'
13:
Output: W1, 01, W2, a2-
Notice that have rank constraint for the Z, in Eq. (5). Suppose singular value decomposition of X_ as X-, V,T with Uj E R ; Dj E R V, E RRx Since D; has full rank, take D,V,Z, and D,V,w, new targets and variables. With slight abuse of notation, then the problem becomes
min
1 W. 2
Σ U. (Ze UZ
w.a,))
(8)
F
In the following, show = 2 is enough to give counter examples. Similarly, using the singular value decomposition of U?U2 as U2 = UDVT with a rectangle diagonal matrix D E RP xps, Notice that U1, U2 are column orthogonal matrices, thus D; I 1, and (i: D = 1) equals the overlapping columns between X_1 and X_2 Finally, the objective becomes
1 1 Z1 a 11 + 2 2
L(W1. W2, 01. az)
Zz w2a tr "id'')
If we fix and a2, can see and are the best rank-1 approximation of (1+D((2-wwar) since w and aj are the solution
arg min [ + D(22 - -wya?) - 11.
Wi.a1
Similarly, wa and a2 the best rank-1 approximation of Zz DT Wiaf)) Empirically, use alternating update method to find the solution in Algorithm ] for two blocks, where SVD(.) is 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, 01, W2, a2 Once the algorithm converges, the first-order condition is satisfied and two eigen- vectors with zero eigenvalue of the Hessian matrix are decided. Moreover, we can also prove that the convergent solution is indeed local minima (detail see Appendix B Otherwise, we examine local minimum using gradient descent or other optimization method started with noise, if necessary.
Based on Algorithm D we find several cases with bad local minima including the overlapping case (3i, D. 1). The results are shown in Table [ We observe distinct gaps between the local minima because our choice of elements in the Z, is small. the non-ov overllallg 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 2,, though we also show bad-min applied with the overlapping data feature in Row 3 in Table
interesting to note that for easily broaden the alternating update method into general d case in Appendix that will also verify similar observation: at most d local minimum produced by a sparse-first-aan first-layer network with hidden d nodes. which leaves 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.
2, only at most two local minimum are found, and we can

---

Under review as a conference paper at ICLR 2021
Table 1: Examples found by algorithm with spurious local minimum. All experiments run 600
iterations, except last one with 1000 iterations. A == X LV
21
Z2
D
A
b1 A2
[V
Objective L
0.5
2.1 10
0 10
< 10 14
0.5143043518476
0
-1
0
0.9
1.-1
0~ 10 14
< 10
0.6781647585271
2
0
0
1
0.8
3.4 10-1
0~ 10
< 10
0.5373672988360
0
-1
-2
0.1
107
0 10
10
0.6805528180352
0
0
1.7-10
0 10 14
< 10
0.8980944246693
1
1
0
0.6
0
205-10-1
0 ~~ 10 10-14
< 10 14
0.4712847600704
2 0
0
0.8
Additionally, a descent algorithm still will diverge to infinity. For instance, the example in Appendix shows that there is sequence diverging to infinity while the function values are decreasing and convergent.
4 LANDSCAPE OF DEEP SPARSE LINEAR NETWORKS
In this section, we briefly extend Theorems and to deep sparse linear networks and leave the proof in Appendix [ The intuition is that deep linear networks have similar landscape property as the shallow case (Lu & Kawaguchi] 2017 Effteharr] 2020). However, understanding the landscape of arbitrary deep sparse linear network is still complicated.
Theorem For a deep sparse linear neural network with scalar output (dy 1) and any sparse structure, every local minimum 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 simple choice for obtaining global minimizer below.
How to obtain global minimizer in scalar case: global minimizer in the two-layer case with a; = 1. then the remaining layers uniformly distribute the output of each node the next layer. For example, if one node has h 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).
One way is to set the first-layer weights as the
Theorem 7 For a deep sparse linear neural network with sparse first layer and dense other layers, assume that X, Y have full column rank, and i + X= =0 If d, Z min(d,, dy Vi 2 1, where d; is the hidden width in the i-th layer, then every local minimum is a global minimum.
Note that under our assumption d; 2 minfd1, dy Vi 2 1, the deep linear network we study has the same solution 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.
DISCUSSION
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 net- work, that is, one generated from low rank constraint, another is produced from sub-sparse struc- ture. 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 meth- ods 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.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. arXiv preprint 0rXiv:1811.01922. 2018.
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis of gradient descent for deep linear neural networks. arXiv preprint arxiv:1810.02281, 2018.
Pierre Baldi and Kurt Horiik. Neural networks and principal component analysis: Learning from examples without local minima. Neural networks, 2(1):53-58, 1989.
Pierre Baldi and Zhiqin Lu. Complex-valued autoencoders. Neural Networks, 33:136-147, 2012.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for convnet with gaussian inputs. arXiv preprint arXiv: [ttv:/00/ 702.07996, 2017.
Miguel Carreira-Perpinale and Yerlan Idelbayev. pruning. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 8532-8541, 2018.
algorithms for neural net
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pp. 248-255. Icee, 2009.
Simon S Du and Wei Hu. Width provably matters in optimization for deep linear neural networks. arXiv preprint arXiv: 01111991117721 2019.
Simon Du, Jason D Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. arXiv preprint arXiv: 18//. 1e11111111000... 2018.
Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. Psychome- trika, 1(3):11-2118 1936.
Armin Eftekhari. Training linear neural networks: Non-local convergence and complexity results. arXiv preprint arXiv:2002.09852 2020.
Utku Evci, Fabian Pedregosa, Aidan Gomez, and Erich Elsen. The difficulty of training sparse neural networks. arXiv preprint arXiv:1906. 10732, 2019.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint arXiv: 1803.0338 2018.
Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks. arXiv 2019.
preprint arXiv:
Rong Ge, Jason D Lee, and Tengyu Ma. Learning one- www-hhiddddeeeee neural networks with landscape design. arXiv preprint arXiv: 1.7711.000 1.00501, 2017.
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. arXiv preprint 15 2015a.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. In Advances in newral information processing systems, pp. 1135-1143, 2015b.
Kenji Kawaguchi. Deep learning without poor local minima. In Advances in neural information processing systems, pp. 586-594, 2016.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip HS Torr. Snip: Single-sho network pruning based connection sensitivity, arXiv preprini arXiv:1810.0230 2018
Dawei Li, Tian Ding, and Ruoyu Sun. On the benefit of width for neural networks: Disappearance of bad basins. arXiv, pp. arXiy-1812, 2018.
Zhuang Liu, Mingjee Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the value of network pruning. arXiv preprint 181iv 2018.

---

Under review as a conference paper at ICLR 2021
Christos Louizos, Karen Ullrich,, and Max Welling. Bayesian compression for deep learning. In Advances in neural information processing systems, pp. 3288-32888 3298, 2017a.
Christos Louizos, Max Welling, and Diederik P Kingma. Learning sparse neural networks through 1_0 regularization. arXiv preprint arXiv:1712.01312, 2017b.
Haihao Lu and Kenji Kawaguchi. Depth creates no bad local minima. arXiv preprint arXiv:/702.08850 2017.
Eran Malach, Gilad Ychudai, Shai Shalev-Shwartz, and Ohad Shamir. Proving the lottery ticket hypothesis: Pruming is all you need. arXiv preprint arXiv:2002. 005000 2020.
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two- layer neural networks. Proceedings of the National Academy Sciences, 15663))77665--777,,, 2018.
Leon Mirsky. Symmetric gauge functions and unitarily invariant norms. The quarterly journal of mathematics, 11(1)500-59, 1960.
Dmitry Molchanov, Arsenii Ashukha, and Dmitry Vetrov. Variational dropout sparsifies deep neural networks. arXiv preprint arXiv:1711.05369 2017.
Itay Safran and Ohad Shamir. Spurious local minima common in two-layer relu neural networks. In International Conference on Machine Learning, pp. 4433-4441. PMLR, 2018.
Andrew M Saxe, James L McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynam- ics of learning in deep linear neural networks. arXiv preprint 132.62/3 2013.
Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah. Weight sharing is crucial to succesful optimization. arXiv preprint wrXiv:1706.0068: 2017.
Ruoyu Sun, Dawei Li, Shiyu Liang, Tian Ding, and Rayadurgam Srikant. The global landscape of neural networks: An overview. IEEE Signal Processing Magazine, 37(5):95-108, 2020.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small nonlinearities in activation functions create bad local minima neural networks. arXiv preprint /802. 004403377.... 2018.
Michael Zhu and Suyog Gupta. To prune, or not to prune: exploring the efficacy of pruning for model compression. arXiv preprint 1rXiv:1710.01878, 2017.
10

---

Under review as a conference paper at ICLR 2021
A DECREASING PATH OF SPARSE LINEAR NETWORK WITH SPARSE FIRST LAYER
In addition, there still exists decreasing path to infinity:
2
W1
min L(w1,.... wa)
Y
X
122
W3
W1
W6
2
W7
Wg
(9)
W1 W/
W1 Wg
Y
X
W22 W.s + Wy
Wg + WyyDg
2
W4 W7
Wa
( ))
-- 1 :) Choose (wi, W2, w3, W4y Was W6, w7, wa) = - (- Vk, 1, Vk 0,1,
X 13, Y
with k N+. then 2L .1...... ws) ming L(w,,..., wg) = 0, hence we get decreasing path to infinity, but not global minimum.
( + 1)² decreases when increases. Since
B ALGORITHM ANALYSIS
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 (wi, aj w aq) satisfy zero gradient. Recall the first-order condition:
0L
(Zi wia + D(22 w2a7)) a1 = (Z1 + D(Z2 w2a?)) a1 afa,.,
dw1
öL
= (2) won + D(22 - w2a²)) WI = (2) + D(22 w2 Wi - w wia
0a1
aL
(Z2
wya T (Zr wia a2 (Zz D² wia a2 a azw2.
Owa
0L
wiaa)) W2 - w/ w2a2. (Z2 - W2a + DJ (Z) - wiaa))² W2 = (Zz + DJ (2) Dz
Da2
(10)
Notice that wi, aj is the best rank-1 approximation of Zı + D(72 waa and w a the best rank-l approximation of Zg + (z a (wi, aj w aς) with zero gradient.
wia Then we have already got a solution
Third, we verify that the convergent solution is a local minimizer through the conditions we checked. Set r1 Z1 + D(Z2 w2a2), ). Zz DT w,a?)) Then
aTaT (-ri (-ri+2waaf)) az
ri + 2w w w Ta D" D'wiag a w Dwold,
a aTD az af 2222pp (-r2 + 2w2a?
Dwzaf w DwwTay, -r 2w2ah
V'L(W1, W2, az)
aIw? Dr
w weldd (11)
Set H" VVWWW ai w az). Observe that (wif. - o", 0²) H' = 0, (0" O", w -a²") - H-= =0
showing that H* has zero eigenvalue with least two eigenvectors V1 (wiT, -at" " Oz)
and v2 (0 0 wxT -
Suppose the third smallest eigenvalue is A 2 > 0, then for any direction with ||v//2 1,
have 0n Vi 02V2 V3V3 with V3 V1, V3 V2, Σi of 1, and w/[[w|12-
11

---

Under review as a conference paper at ICLR 2021
If as # O, then vHv anv3HV, 2 az²s 2 age 2 0. Otherwise, with small 51, 62 as perturbation, and the perturbed parameters are notated as W1. a1. W2. 02 = (1 - 5i. (1-1(1122)1 6 (1 + j (1 82)aς, which yields
d1v1 + 82V2
L(WI, â1, W2, ā2)
|Xx (Z - (1 89) w(a X2 (Z2 (1 82 (2) 112
|Xx (Z) wiaa)) X2 (Ze w2a,)) 113 + 1103 w i + 02 22 11:
+ 20 tr((w[af) (ri wla ] + 20 tr (w2a? T (r2 W2a )
|[] (Z) w/aa X2 (Zz w2a4) 11 1 of + 83
L(W1, 01, W2, a2) + af + 8 80 w22 1P 2 L(w1, 01 W2. 02). 01,
(12)
Third equality holds for the rank-l approximation of the solution. Hence, the convergent solution is local minimizer.
Fourth, due to numerical error, we can not obtain exact convergent solution, but we are able obtain approximate solution (wi. aj, a²)aa) after iterations with L (wf, af w a?) L (wi, aj, W2, 05) < e², and then use Weyl's inequality (Safran & Shamir, 2018 Theorem 2),
\ a'i, w2. a5)) A, L(w]. aj. w2, a5)) O(e),
where (H) is the i-th smallest cigenvalue 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.
C USELESS CONNECTIONS AND NODES IN SPARSE NETWORK
In this section, we explain several kinds of unnecessary connections suffered from sparsity or net- work pruning.
Input layer
Hidden layer
Hidden layer
Output layer
h
h
42
h13
h3
12
43
Figure 3: An example of sparse network with no bias. Lines are connections of original sparse network, dotted lines are useless connections that can be removed, and solid lines are effective connections.
1. Zero out-degree I: if a node have zero out-degree, such (2) in Figure 3 the input connections.
eliminate
2. Zero out-degree if a node have zero out-degree when removed output connections in latter layers, such as (1 in Figure Though it owes one output connection, the connected node (2) is zero out-degree, hence the connection can be removed, leading zero out-
degree. We can eliminate the input connections of i1) as well.
3. Zero in-degree I: if a node have zero in-degree, such as h and h (1) in Figure we can eliminate the output connections, but notice that when the node has bias term, then can not remove output connections since the bias constant will still propagate to subsequent layers.
12

---

Under review as a conference paper at ICLR 2021
4. Zero in-degree II: if a node have zero in-degree when removed input connections in former layers, such h:g in Figure Though owes one input connection, the connected node ( is zero in-degree, hence the connection can be removed, leading to zero in-degree. We can eliminate the output connections hig)) as well.
D GENERAL BLOCKS ALGORITHM
Algorithm 2 Sparse-d-Opt (X1, Xa. Zi.... Za): Obtain the solution of two-layer sparse lin- ear neural network with d hidden neurons.
1: Input: Input matrix X1.... Xa. Target matrix Zi.... Zdi
2: Initialize W,. di, ag = 2, .....,d;
3: while not conterge do
4: for L,..... do
5: Wi, Wi,di, a; SV D(Z + E -xx,(2-d,wwaf)))
6: end for
7: end while
8: w, dww,ti= d.
9: if Ar (V² \v(LL)) R 0, A441 LV > 0 then
Return the solution W,, a;, 1.....d.. ,d.
11: else
12: Try again from another initialization.
13: end if
14: Output: w,, a,, = I.....d.. d.
The analysis that the convergent solution 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
(1 1)
--1 -
22
Zs
1.0
0.0
-0.088
-0.599
-0.234
0.178
0.0
1.0
-0.163
0.429
-0.529
0.431
Training data: XTX
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
-0.0
0.178
0.431
0.193
-0.244
-0.0
1.0
Local minimum found:
Table 2: Examples found by algorithm with spurious local minimum when d, 3. All experiments
run 2000 iterations. A; == 2x
Ad+1
Ag....,A4 Ad
VL 2
Objective L
1.9 10
0 10
< 10
0.357481957
9.7 10-2
0~ 10-14
< 10-14
0.521705675
4.9 10
0~ 10-14
< 10-14
0.539730382
E MISSING PROOFS FOR SECTION 2
E. PROOF OF THEOREM 3
Proof: Suppose the j-th node has full out-degree and one in-degree, so that w E R. We treat objective with fixed other weights and only consider optimizing w-j, a.j
min (Wi, a,) y x_ w,a,
1
x_ywaa
V v Σ x_
(13)
i
13

---

Under review as a conference paper at ICLR 2021
Based the proof of scalar case, local minimizer (wz.a7) a3) of f(W,, a,) must satisfy the condition
x Y -xXxx,wja") O, showing that a(w3,a7) 211 - Px_,)) 3 Therefore, the
objective with remaining weights becomes:
1
min W-s.a.,17)
(1 ( Px_,
(1 - - inj
(14)
2
We define (ln--x - .) Xs,, (In - Px Y) as new training dataset which is the projection into the orthogonal complement of X-j. and remove some elements in w-, corresponding to the column in X-j. Moreover, if X has full column rank, then projected data (In Px_,) Xs, 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)
Y Σ X_ Σ
x agl
+ 12- Σ
X_ -0:- Σ
X
,
W 15
ER
JER
SER2
jER
Under similar analysis as scalar case,
Vi R1, XT,
Y1 Σ X_,w-1as1 Σx DX--W-jaj
=0.
iER1
JER
Vi R2 X
Y2 Σx_,
X w- ;12 Σx
X W ,0
=0.
IER2
JER
Hence,
W W-i: 0igl
W 01,1
X , X-((81)
Yi Y Σx,w-Ja0 ER.
:
JER
W-( 0ipR111 1/
W-i. 0:,2
:
w 0i,2
-x ,
.
Y2 - Σ Xx-w--jap
1 R2.
JER
W-4 ( Gipz,
Then the objective becomes:
|1--
(an)nn--- EX- 50j1
(In ( Px
-
+ (In ( Px Px
Y/2 Xx-xx,w-j0pp
JER
JER
We can see the objective is separated into two parts with shared sparse first-layer weights. Notice that if i &f Tı, then X, XT,, hence (In Px_ X; 0. Therefore, we simplify the problem as
min L(W A) W.A
1
[In Px 7,)
---Xx
Yi Y- Σ X₁ Σ
Wijaj1
2
iET.
jugS;
(15)
+
(In (
Y2
Σ
X; Σ
Wijagz
2
juidS,
14

---

Under review as a conference paper at ICLR 2021
Use previous analysis again Ti T2 in first output dimension and Tz \ Ti in second output dimension since no overlap in parameters by the condition U(7 n T2) n ( T2) = and u(Ti n n2 \ Ti) 0. Therefore, we simplify the problem again
min L(W, A) W,A
nn2 1 (I- oi )xTTVV)) (In nn mi)
Y
Σ iETinTa
X Σ
Wij
2
J:
+
1
In In-P((1a (l-PP( (1--P(1--X P ) (In PPx
Y2- iETiNTa
Σ
X;
2
jugs,
Using the fact that (4, - Pw:) (In Pww))= = - -P(Wi, if W₂ = 0. Hence the remaining problem is same
2 (In Px-
min L( A) W.A
Yk
Σ
X,
Σ
Wijajk
2
iETiNTa
Therefore, the remaining network structure has dense second layer.
F MISSING PROOFS FOR SECTION 4
The objective of a deep linear network with squared loss is
min WO WOO,...,Woo)).
G - - -.......W(U) ..
(16)
where the i-th layer weight matrix W E Rd--ixd, do = dz, d2 = dg Data matrix X e Raxds, Y E Ruxdy, We adopt s/D {k W = 0} as pruned dimensions in j-th column of W Besides, ih j.-s as the remaining j-th column i-th layer weight which leaves out pruned
dimension set S. For simplification, we denote ())
S- E R (d-11-15)) (d
())
-1-111))))) wikk
W(O jk
and ( the pruned weight matrix with several zero elements before.
F. PROOF OF THEOREM
Proof: Using induction. Base on Theorem ! have already proof two layer case. the result holds for (L 1)-layer sparse linear network, we consider layer case. denote Xnew == XW(1) as new training set, and l == (1) ... (L), Then based on inductive assumption, e Xnew 0, showing that
Fx_ O. v1 sissaa d1.
(17)
Combined with first-order condition:
0L
ET X_; w(L)); 0.
dw 11)
If (W())... W((1)) * O, then e O, which satisfies the global minimizer condition. Other- wise, any value of w _h doesn't 't change the loss since the forward path already contribute zero to the
final output. Hence, arbitrary choice of (!!) owes same objective value. Thus, from Eq. 17). we still obtain éT' x"x=; = Thus any local minimum is a global minimum for the pruned sparse model.
15

---

Under review as a conference paper at ICLR 2021
F.2 PROOF OF THEOREM 7
Proof: Since Vi j.,, share no same columns and x"X X = Lı. then v j. x
0. Besides, from our assumption Sf=1S, 0. then nz= {1...., d), meaning that
(X-1, 1, X-a) is X with different arrangement of columns. Hence
d
Y = PxY + Px)x XXX - Σ
x x + (T -xx),, (18)
Set ((2) = (ai,.... Odly ]", then the objective becomes
dg
Z w- (3() W( 1
We set X = XW = (X..--....;; X-d, w-d1). Now we show the following problems have same local minimizer condition for w-1-
(P) (WW,,,ae w(1) Y-X (I(C)...w(c)))
(19)
(P1) L.W, A) Y Σ x a
there a local minimizer w w-1...., W-d, * 0, for problem (P), since d, 2 (dj. d.j.dd.... d, Vi 2
and X, Y have full column rank, then based Theorem 2.3 in Lu & Kawaguchi 2017). local minimizer of L(W(1) W(2) ,.... W(T) is obtained when
2 (()) (XTX) X
Notice that XTX diag( w W -l,,.... w. di w w-d,). Then the objective simplified as
2L(W(W)= y Y -x -x(XTX) xTy
(X : -X-W_w
Y
w W_,W- W-
i=1
di
X_, (X-ww-i) -[--WWWJ :w x==7
(20)
W W-i
ZZ Σ X-,2, X- W Z
w w-
For problem (P1), similarly, local minimizer of L2(W, (A) is obtained when
(X_)w-,)" (v Edi -i=l X __ 0. objective as
Then of
(X_,w -_, " showing same loss w
(X_,w -_ (W TY
(T) Y
W
1=1
(21)
dj
(X_,w (X ' 1 - 2T (W()..
2
X-
w W w
Finally, based on Theorem 2 every local minimum of (PI) is global minimum. Hence every local minimum of (P) is global minimum.
there exists ig, such that w in = 0, we show that Z,, = below. Without loss of generality, we assume in 1, then the value of a does not affect the objective, take a 0 well. In order
16

---

Under review as a conference paper at ICLR 2021
to show the result, we only perturb w-1, d1, W ..... W into w-1 Aw, ai + Aa, W(3)
A ,I(L) + A and analyze the difference of loss as AT. We set
AW II 1=3
W + +4.)
II W W
W(
(22)
Then the perturbation leads to
2AL(Aw, Aa, AW) 1 AwAn (Wo AW) || - 1
+ Σ
7 w- (W + AW) 1| 1 w- Wo
##1
(23)
= - [Z AwAn (W" + AW) + AwAa (W" + AW) |
tr trW a (Z, w aa W + la AW
i#1
Applying the first case to the remaining parameters excluding w-1 and aj (If there are several w-18 are zero, we can leave them all out), we have
a To (X-iw T
(w-;)
W W-,w W-
w w-,--
which agrees with
w (Z; - w w_ Wo)
Hence the second term in the final row of Eq. 23 is zero. Besides, let us note the first-order term
of Aw, showing that tr [r AwAa (Wo + AW ] 0. Otherwise, given w O((="), a-1
(t=-)), AW O(t-3), as + oo, the sign the final expansions of Eq. 23 depends on the fist term that is indefinite.
Therefore, Aa (Wo AW) zf = 0, then (wo AW) of
0, leading to Wo and
AWZ[ O.
In view of expression AW, holds that
AW =
(3)
.... AW wll) of +...
3
(24)
1.-2
Σ Ar)...
where fe(Ag..... Ar) is the sum of the product W3 W(L), Ag...., AS that con- tains exactly t different A,s. Then from small-order terms to high-order terms, we obtain fi(Aa...... Ar)Z, 0. It follows from fL-2 A3 ....... Az, de 2 min(dj, d and the arbitrary of A. A get Z; = 0. Finally, when Zı 0. is evident that W1 0 already satisfies the global minimizer condition since the objective is separated as Ed - 1| a (3).... W(L) | This completes the proof.
17


Reviews:
[{"review_id": "n9yGBO3v817", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the 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.\n\nOverall, I vote for rejection. The proofs are detailed and seem correct. However, I was worried that (1) the proofs make incremental contribution compared with two existing works; (2) assuming activations are linear is too strict; (3) the insight given by the theorems is not clear; and (4) the applicable domain is not clear.\n\nPros:\n\n+ The authors prove that (1) sparse linear networks do not have any spurious local minima under some assumptions; and (2) for two-layer sparse linear networks, the previous properties do not stand anymore when the assumptions no longer hold. The authors have given detailed proofs for their arguments.\n\nCons: I was concerned about the technical novelty and significance. They are not justified in this paper.\n\n- From technical aspects, the proves are simple extensions of existing works on linear neural networks; such as Kawaguchi (2016) and Lu & Kawaguchi (2017). The authors do not state clearly what new proof techniques are used in this paper.\n\n- This paper assumes all activations are linear and then proves in many cases spurious local minima do not exist. However, most neural networks in practice _have_ nonlinear activations. Some papers have suggested the nonlinearity in activations significantly change the loss landscape, such as [1-3] amongst others. I understand that it would be good to study a simpler model when a comprehensive model is intractable. But the simpler model needs to share similar properties with the real-world case. The three aforementioned papers concern me. \n\n- The insights of the given theories are not clear. Did the authors hope to suggest pruning would bring something new into linear networks? It would be good if the authors can clearly discuss this and give some potential practical implications.\n\n- The potential application would be limited. Understanding the loss landscapes of sparse linear networks is important if we need to train them from scratch. However, most pruning methods are applied when neural networks have been trained. Some works even do not need fine-tuning after pruning. This undermines the importance of this paper.\n\nQuestions: It would be good if the authors can comment on the cons.\n\n[1] Yun, C., Sra, S., and Jadbabaie, A., “Small nonlinearities in activation functions create bad local minima in neural networks,” ICLR 2019.  \n[2] He, F., Wang, B., and Tao, D., “Piecewise linear activations substantially shape the loss surfaces of neural networks,” ICLR 2020.  \n[3] Goldblum, M., Geiping, J., Schwarzschild, A., Moeller, M., and Goldstein, T., “Truth or backpropaganda? An empirical investigation of deep learning theory,” ICLR 2020.", "extra_scores": {}, "extra_text": {}}, {"review_id": "fpj1WPfqewq", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n\nThis paper considers the optimization landscape of sparse linear networks. Under the regression setup (squared error loss), the paper shows that there is no spurious local minimum in the training loss (as in the dense linear networks) if:\n1) The output label is scalar ($d_y = 1$), or\n2) The data matrix $X \\in \\mathbb R^{n \\times d_x}$ has orthogonal columns, only the first layer of the network is sparse, and each input node is connected to only one hidden node in the first hidden layer (similar to non-overlapping filters in convnets).\n\nIf these conditions are not met, there may be bad local minima caused by the sparsity of the network. The paper gives some examples:\n1) For $d_y = 3$, the paper gives a counterexample sparse network that has a bad local minimum.\n2) For $d_y = 2$ (and higher), the paper proposes an iterative algorithm that looks for local minima of the sparse neural network, and it verifies by experiments that bad local minima exist.\n\nStrength\n\nAlthough sparse neural networks and network pruning has received much attention, our understanding of sparse models from the optimization point of view is limited. It is good to have some results in this field. I value the theoretical investigations done in this paper, and I’m also a bit surprised that there is such a stark contrast between the cases $d_y = 1$ and $d_y > 1$. The paper essentially tells us that sparse linear networks have benign loss landscapes as in the dense linear networks if the output is scalar (Theorem 1 & 6), but suffer bad local minima when $d_y > 1$ unless some strong conditions are satisfied.\n\nWeakness\n\nAlthough I find the observations in this paper interesting, I cannot stop questioning whether the analysis done in this paper is really meaningful or useful. It is known that there is already a big gap between linear networks (i.e., without nonlinear activation functions) vs nonlinear networks (i.e., with nonlinear activations), in terms of the “no bad local minima” property. Linear networks (under some width conditions) have no bad local minima, but nonlinear networks do have bad local minima. Intuitively speaking, sparsifying network weights will “hurt” the loss landscape. Given that nonlinear networks already have bad local minima even before sparsifying, it is natural to expect that sparse nonlinear networks will also have bad local minima. My question is, what kind of insight does the paper provide for nonlinear networks, other than the (already expected) conclusion that “sparse nonlinear networks likely have bad local minima”? In my humble opinion, the significance of the analysis in this paper looks rather limited and it does not provide new insights that carry over to sparse nonlinear networks.\n\nIn addition, the clarity of the paper requires improvement. Before reading the paper, I found it very difficult to parse the abstract, especially the conditions (e.g., “non-intersected sparse first layer and dense other layers with orthogonal training data”) in 1) and 2). It would be better to elaborate more on these conditions. Also, I found the results in Section 2.4 difficult to understand; I think the statements of Theorems 3 and 4 are not clear enough. The terms “some projected data”, “influence for spurious local minima” are not defined nor clear. What is “the same local minimum” in Theorem 4 referring to? A more high-level question is: how are these results related to the existence of bad local minima? In Theorem 7, I couldn’t find the dimensions $d_i$ defined anywhere in the main text.\n\nAlthough it is claimed in the abstract that “no unrealistic assumptions” are made, I believe the conditions in Theorems 2 and 7 are quite strong. The theorems require that a) the data matrix $X$ has orthogonal columns, b) only the first layer of the network is sparse, and c) each input node is connected to only one hidden node in the first hidden layer. I believe these conditions are not likely to arise in practice. It’d be great if you can provide more justifications on these set of conditions.\n\nOverall assessment\n\nAlthough the paper makes some contributions to the understanding of the sparse linear networks, I believe the significance of the results are rather limited and they do not provide additional insights. I lean towards rejection.\n\nMinor comments\n- The paper is structured in a way that all results on shallow networks are presented first and then some of them are extended to deep networks. However I had the false impression that all the results only hold for shallow networks before reaching Section 4, which is at the end of the paper. I think it’d be good to have a remark after Theorems 1 and 2 that they are extended to deep networks in a later section.\n- In Section 3, is it difficult to construct some counterexamples ($d_y = 2$) with bad local minima, instead of using an iterative algorithm to find them? It’d be good if you can show that the conditions in Theorems 2 and 7 are necessary.\n- Fig 2: typos in hidden node superscripts?\n- Pg 7, first line: Eq. (5) -> Eq. (7)?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "cD9uyN76eE", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the 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.\n\nThe main contributions of this paper can be summarised as follows:\n\n(1) If the network has a scalar output, then every local minimum is global (Theorem 1 for two-layers and Theorem 6 for multiple layers).\n\n(2) The same conclusion (every local min is global) holds if the network has two outputs under extra assumptions (non-overlapping first layer weights and orthogonal data).\n\n(3) If the network has at least three outputs, it is possible to build counterexamples with spurious local minima (Theorem 5 gives one such counterexample and the algorithm in Section 3 gives even more of them).  \n\nOverall, although the study of the landscape of sparse linear networks is an interesting topic, the submission is not particularly insightful in this regard. The results are quite weak and only show that spurious local minima can occur as soon as the output dimension is 3 (while they provably do not occur in lower output dimensions). The positive results for two-layer networks follow from a straightforward analysis and they can be extended to multiple layers as done in the related literature (Lu & Kawaguchi, 2017; Eftekhari, 2020). The negative results consist in presenting a counterexample.\n\nThe main weaknesses of the submission are as follows:\n\n(1) The paper does not really explain why neural networks can be pruned so well. It just proves that the landscape can be bad.\n\n(2) The analysis is quite straightforward and does not enough elements of novelty over existing work.\n\nOne way to obtain more insightful results would be to consider a less general setting. In the current version, the authors prove that spurious local minima exists for some initialization and for some data distribution. Does the same conclusion hold for \"most\" data distribution (say a Gaussian input distribution) or \"most\" initializations (say Xavier's initialization)? Proving such a statement may lead to significantly more interesting results.", "extra_scores": {}, "extra_text": {}}, {"review_id": "6pszxx4mT2", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provides an interesting analysis and direction to understand landscape of deep linear networks with sparsity patterns. In terms of main technical contributions, the authors prove that every local minimum is a global minimum in the case of scalar output with any sparsity structure, and show the existence of sub-optimal local minima in the case of high-dimensional output, analytically by considering a simple shallow network with a simple sparsity structure, and numerically by investigating the solutions found by an algorithm that converges to a local minimum.\n\nUnderstanding deep linear networks is an important topic for several reasons. One reason is that deep linear networks change its NTK during training, unlike the unrealistic deep nonlinear networks in the regime of extreme over-parameterization. Deep nonlinear networks in the regime of extreme over-parameterization have been studied in the regime of extreme over-parameterization, or so-called NTK regime. However, we know now that deep nonlinear networks in the regime of extreme over-parameterization is indeed shallow linear models with a fixed kernel, or a fixed NTK. In other words, analyzing deep nonlinear networks in the regime of extreme over-parameterization is reduced to analyze classical shallow linear models, which is trivial in terms of theory. Moreover, from practical viewpoint, we know that practical deep neural networks change NTK during training, which seems to be one of the main sources of inductive bias to allow deep networks to perform well. To understand neural network in the practical regime beyond the NTK regime, for example, deep linear network with one hidden layer was recently studied in https://arxiv.org/abs/2003.02218.  \n\nIn sum, understanding deep linear networks is currently revisited and of the great importance in the literature, as we now realize that deep nonlinear networks in extreme over-parametrization regime or NTK regime are simply shallow linear models. Given this context, I think this paper provides an interesting and important contribution to the literature.\n\nThe proof of Theorem 5 makes sense. Due to the sparsity pattern, we cannot escape from w_4 = 2_8 = 0 without increasing the loss value in the sufficiently small neighborhood. \n\nOn the other hand, the particular construction used in the proof of Theorem 5 is not general in the following sense. Given this target matrix Y and this sparse network, w_3 and w_7 are unnecessary, and we know a priori that we should make w_3 and w_7 to be zero. Indeed, the existence of the sub-optimal local minima is shown by relying on the nonzero w_3 and w_7 in the proof. An interesting question to further improve the paper would be the following: can we construct suboptimal local minima with w_3 = w_7 = 0 in this example? With w_3 = w_7 = 0, the perturbations of w_4 and w_8 can always decrease the loss value by making w_4 * w_8 closer to 4. \n\n\nMinor comments:\n\n- if the term “sub-network” is used in the statement of the theorems, it should be more formally defined somewhere. I could understand what it means by reading the proof.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies optimization landscapes arising the fitting of sparse linear networks to data. It argues that for scalar outputs, every local minimum is global, while for d >= 3 dimensional outputs, there can be spurious local minimizers. The paper also argues that similar results hold for deep networks. Counterexamples on the existence of non-global local minimizers are constructed analytically and corroborated by probing the optimization landscape experimentally. 

Pros and cons:

[+] Network sparsification is an important practical problem, and there are relatively few theoretical guidelines on when and how sparsification can be achieved. In particular, results that help to explain why trained networks are often sparsifiable and/or provide theoretical guarantees for sparsification algorithms would be significant. 

[-] Reviewers raised concerns about the significance of the paper’s results. In particular, they found it difficult to connect the paper’s analysis of landscapes of linear networks to the question of when and why practically occurring networks can be pruned. They also had difficulty isolating new ideas in the mathematical analysis beyond previous works on the landscape of linear networks. Finally, several reviewers expressed concerns about the extent to which the paper’s observations on linear networks generalize to nonlinear networks.

[-] Reviewers raised concerns about the clarity of the paper. The mathematical exposition is unclear in places: conditions are not clearly stated, terminology is occasionally vague. Moreover the paper’s handling of optimality conditions for constrained optimization problems is unclear (e.g., the proof of Theorem 6 uses the unconstrained optimality condition $\ell^T X = 0$ in the inductive step, even though the inductive hypothesis pertains to a constrained problem). 

[-] The technical results make assumptions that are occasionally quite strong. For example, Theorem 7 requires orthogonality of the data matrices, when restricted to indices where the weights are nonzero. As reviewers note, this assumption seems highly restrictive.  

Overall, the paper addresses a topic that is important to the ICLR community: developing theoretical analyses of network sparsification. However, the significance of its results is not clear, and the technical exposition would need significant improvement to meet the bar for publication. 
Decision: Reject